iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/978-3-030-60440-0_15
Computing Subset Transversals in H-Free Graphs | SpringerLink
Skip to main content
Springer Nature Link
Log in

Computing Subset Transversals in H-Free Graphs

  • Conference paper
  • First Online:
Graph-Theoretic Concepts in Computer Science (WG 2020)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 12301))

Included in the following conference series:

  • 493 Accesses

Abstract

We study the computational complexity of two well-known graph transversal problems, namely Subset Feedback Vertex Set and Subset Odd Cycle Transversal, by restricting the input to H-free graphs, that is, to graphs that do not contain some fixed graph H as an induced subgraph. By combining known and new results, we determine the computational complexity of both problems on H-free graphs for every graph H except when \(H=sP_1+P_4\) for some \(s\ge 1\). As part of our approach, we introduce the Subset Vertex Cover problem and prove that it is polynomial-time solvable for \((sP_1+P_4)\)-free graphs for every \(s\ge 1\).

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

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Abrishami, T., Chudnovsky, M., Pilipczuk, M., Rzążewski, P., Seymour, P.: Induced subgraphs of bounded treewidth and the container method. CoRR, abs/2003.05185 (2020)

    Google Scholar 

  2. 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, Cham (2020)

    Google Scholar 

  3. Bonamy, M., Dabrowski, K.K., Feghali, C., Johnson, M., Paulusma, D.: Independent feedback vertex set for \(P_5\)-free graphs. Algorithmica 81, 1342–1369 (2019)

    Article  MathSciNet  Google Scholar 

  4. Brandstädt, A., Kratsch, D.: On the restriction of some NP-complete graph problems to permutation graphs. In: Budach, L. (ed.) FCT 1985. LNCS, vol. 199, pp. 53–62. Springer, Heidelberg (1985). https://doi.org/10.1007/BFb0028791

    Chapter  Google Scholar 

  5. Brettell, N., Horsfield, J., Munaro, A., Paesani, G., Paulusma, D.: Bounding the mim-width of hereditary graph classes. CoRR, abs/2004.05018 (2020)

    Google Scholar 

  6. 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)

    Article  MathSciNet  Google Scholar 

  7. Chitnis, R., Fomin, F.V., Lokshtanov, D., Misra, P., Ramanujan, M.S., Saurabh, S.: Faster exact algorithms for some terminal set problems. J. Comput. Syst. Sci. 88, 195–207 (2017)

    Article  MathSciNet  Google Scholar 

  8. Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Subset feedback vertex set is fixed-parameter tractable. SIAM J. Discrete Math. 27, 290–309 (2013)

    Article  MathSciNet  Google Scholar 

  9. 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. To appear

    Google Scholar 

  10. Dabrowski, K.K., Johnson, M., Paesani, G., Paulusma, D., Zamaraev, V.: On the price of independence for vertex cover, feedback vertex set and odd cycle transversal. In: Proceedings of the MFCS 2018. LIPIcs, vol. 117, pp. 63:1–63:15 (2018)

    Google Scholar 

  11. Földes, S., Hammer, P.L.: Split graphs. Congressus Numerantium 19, 311–315 (1977)

    MathSciNet  MATH  Google Scholar 

  12. Fomin, F.V., Heggernes, P., Kratsch, D., Papadopoulos, C., Villanger, Y.: Enumerating minimal subset feedback vertex sets. Algorithmica 69, 216–231 (2014)

    Article  MathSciNet  Google Scholar 

  13. Golovach, P.A., Heggernes, P., Kratsch, D., Saei, R.: Subset feedback vertex sets in chordal graphs. J. Discrete Algorithms 26, 7–15 (2014)

    Article  MathSciNet  Google Scholar 

  14. 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 2019, pp. 1257–1271 (2019)

    Google Scholar 

  15. Hols, E.C., Kratsch, S.: A randomized polynomial kernel for subset feedback vertex set. Theory Comput. Syst. 62(1), 63–92 (2018)

    Article  MathSciNet  Google Scholar 

  16. Iwata, Y., Wahlström, M., Yoshida, Y.: Half-integrality, LP-branching, and FPT algorithms. SIAM J. Comput. 45(4), 1377–1411 (2016)

    Article  MathSciNet  Google Scholar 

  17. Jaffke, L., Kwon, O., Telle, J.A.: Mim-width II. The feedback vertex set problem. Algorithmica 82(1), 118–145 (2020)

    Article  MathSciNet  Google Scholar 

  18. Johnson, M., Paesani, G., Paulusma, D.: Connected vertex cover for \((s{P}_1+{P}_5)\)-free graphs. Algorithmica 82, 20–40 (2020)

    Article  MathSciNet  Google Scholar 

  19. Kakimura, N., Kawarabayashi, K., Kobayashi, Y.: Erdős-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing. In: Proceedings of the SODA 2012, pp. 1726–1736 (2012)

    Google Scholar 

  20. Kawarabayashi, K., Kobayashi, Y.: Fixed-parameter tractability for the subset feedback set problem and the S-cycle packing problem. J. Comb. Theory Ser. B 102(4), 1020–1034 (2012)

    Article  MathSciNet  Google Scholar 

  21. Kratsch, S., Wahlström, M.: Representative sets and irrelevant vertices: new tools for kernelization. In: Proceedings of the FOCS 2012, pp. 450–459 (2012)

    Google Scholar 

  22. Lokshtanov, D., Misra, P., Ramanujan, M.S., Saurabh, S.: Hitting selected (odd) cycles. SIAM J. Discrete Math. 31(3), 1581–1615 (2017)

    Article  MathSciNet  Google Scholar 

  23. Lokshtanov, D., Vatshelle, M., Villanger, Y.: Independent set in \({P}_5\)-free graphs in polynomial time. In: Proceedings of the SODA 2014, pp. 570–581 (2014)

    Google Scholar 

  24. Minty, G.J.: On maximal independent sets of vertices in claw-free graphs. J. Comb. Theory Ser. B 28(3), 284–304 (1980)

    Article  MathSciNet  Google Scholar 

  25. Misra, P., Raman, V., Ramanujan, M.S., Saurabh, S.: Parameterized algorithms for Even Cycle Transversal. In: Golumbic, M.C., Stern, M., Levy, A., Morgenstern, G. (eds.) WG 2012. LNCS, vol. 7551, pp. 172–183. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34611-8_19

    Chapter  Google Scholar 

  26. Papadopoulos, C., Tzimas, S.: Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs. Discrete Appl. Math. 258, 204–221 (2019)

    Article  MathSciNet  Google Scholar 

  27. Papadopoulos, C., Tzimas, S.: Subset feedback vertex set on graphs of bounded independent set size. Theoret. Comput. Sci. 814, 177–188 (2020)

    Article  MathSciNet  Google Scholar 

  28. Poljak, S.: A note on stable sets and colorings of graphs. Commentationes Math. Univ. Carol. 15, 307–309 (1974)

    MathSciNet  MATH  Google Scholar 

  29. Sbihi, N.: Algorithme de recherche d’un stable de cardinalité maximum dans un graphe sans étoile. Discrete Math. 29(1), 53–76 (1980)

    Article  MathSciNet  Google Scholar 

  30. Speckenmeyer, E.: Untersuchungen zum Feedback Vertex Set Problem in ungerichteten Graphen. Ph.D. thesis, Universität Paderborn (1983)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Durham University, Durham, UK

    Nick Brettell, Matthew Johnson, Giacomo Paesani & Daniël Paulusma

Authors
  1. Nick Brettell
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Matthew Johnson
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Giacomo Paesani
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Daniël Paulusma
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Nick Brettell .

Editor information

Editors and Affiliations

  1. University of Leeds, Leeds, UK

    Isolde Adler

  2. University of Leeds, Leeds, UK

    Haiko Müller

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Brettell, N., Johnson, M., Paesani, G., Paulusma, D. (2020). Computing Subset Transversals in H-Free Graphs. In: Adler, I., Müller, H. (eds) Graph-Theoretic Concepts in Computer Science. WG 2020. Lecture Notes in Computer Science(), vol 12301. Springer, Cham. https://doi.org/10.1007/978-3-030-60440-0_15

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-60440-0_15

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-60439-4

  • Online ISBN: 978-3-030-60440-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation