Abstract
For the Odd Cycle Transversal problem, the task is to find a small set S of vertices in a graph that intersects every cycle of odd length. The Subset Odd Cycle Transversal requires S to intersect only those odd cycles that include a vertex of a distinguished vertex subset T. If we are given weights for the vertices, we ask instead that S has small weight: this is the problem Weighted Subset Odd Cycle Transversal. We prove an almost-complete complexity dichotomy for Weighted Subset Odd Cycle Transversal for graphs that do not contain a graph H as an induced subgraph. Our general approach can also be used for Weighted Subset Feedback Vertex Set, which enables us to generalize a recent result of Papadopoulos and Tzimas.
The research in this paper received support from the Leverhulme Trust (RPG-2016-258).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Proofs of Lemmas 1–4 are omitted for space reasons. A full version of this paper can be found at https://arxiv.org/abs/2007.14514.
References
Abrishami, T., Chudnovsky, M., Pilipczuk, M., Rzążewski, P., Seymour, P.: Induced subgraphs of bounded treewidth and the container method. In: Proceedings of the SODA, pp. 1948–1964 (2021)
Bergougnoux, B., Papadopoulos, C., Telle, J.A.: Node multiway cut and subset feedback vertex set on graphs of bounded mim-width. In: Adler, I., Müller, H. (eds.) WG 2020. LNCS, vol. 12301, pp. 388–400. Springer, Heidelberg (2020). https://doi.org/10.1007/978-3-030-60440-0_31
Brettell, N., Johnson, M., Paesani, G., Paulusma, D.: Computing subset transversals in \({H}\)-free graphs. In: Adler, I., Müller, H. (eds.) WG 2020. LNCS, vol. 12301, pp. 187–199. Springer, Heidelberg (2020). https://doi.org/10.1007/978-3-030-60440-0_15
Chiarelli, N., Hartinger, T.R., Johnson, M., Milanič, M., Paulusma, D.: Minimum connected transversals in graphs: New hardness results and tractable cases using the price of connectivity. Theoret. Comput. Sci. 705, 75–83 (2018)
Dabrowski, K.K., Feghali, C., Johnson, M., Paesani, G., Paulusma, D., Rzążewski, P.: On cycle transversals and their connected variants in the absence of a small linear forest. Algorithmica 82, 2841–2866 (2020)
Fomin, F.V., Heggernes, P., Kratsch, D., Papadopoulos, C., Villanger, Y.: Enumerating minimal subset feedback vertex sets. Algorithmica 69, 216–231 (2014)
Grzesik, A., Klimošová, T., Pilipczuk, M., Pilipczuk, M.: Polynomial-time algorithm for maximum weight independent set on \(P_6\)-free graphs. In: Proceedings of the SODA, pp. 1257–1271 (2019)
Johnson, M., Paesani, G., Paulusma, D.: Connected Vertex Cover for \((s{P}_1+{P}_5)\)-free graphs. Algorithmica 82, 20–40 (2020)
Lozin, V., Malyshev, D., Mosca, R., Zamaraev, V.: Independent domination versus weighted independent domination. Inf. Process. Lett. 156, 105914 (2020)
Munaro, A.: On line graphs of subcubic triangle-free graphs. Discret. Math. 340, 1210–1226 (2017)
Paesani, G., Paulusma, D., Rzążewski, P.: Feedback vertex set and even cycle transversal for \(H\)-free graphs: finding large block graphs. CoRR abs/2105.02736 (2021)
Papadopoulos, C., Tzimas, S.: Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs. Discret. Appl. Math. 258, 204–221 (2019)
Papadopoulos, C., Tzimas, S.: Subset feedback vertex set on graphs of bounded independent set size. Theoret. Comput. Sci. 814, 177–188 (2020)
Poljak, S.: A note on stable sets and colorings of graphs. Comment. Math. Univ. Carol. 15, 307–309 (1974)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Brettell, N., Johnson, M., Paulusma, D. (2021). Computing Weighted Subset Transversals in H-Free Graphs. In: Lubiw, A., Salavatipour, M., He, M. (eds) Algorithms and Data Structures. WADS 2021. Lecture Notes in Computer Science(), vol 12808. Springer, Cham. https://doi.org/10.1007/978-3-030-83508-8_17
Download citation
DOI: https://doi.org/10.1007/978-3-030-83508-8_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-83507-1
Online ISBN: 978-3-030-83508-8
eBook Packages: Computer ScienceComputer Science (R0)