Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs | SpringerLink
Skip to main content
Springer Nature Link
Log in

Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs

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

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13453))

Included in the following conference series:

Abstract

Paths \(P^1,\ldots ,P^k\) in a graph \(G=(V,E)\) are mutually induced if any two distinct \(P^i\) and \(P^j\) have neither common vertices nor adjacent vertices. The Induced Disjoint Paths problem is to decide if a graph G with k pairs of specified vertices \((s_i,t_i)\) contains k mutually induced paths \(P^i\) such that each \(P^i\) starts from \(s_i\) and ends at \(t_i\). This is a classical graph problem that is NP-complete even for \(k=2\). We introduce a natural generalization, Induced Disjoint Connected Subgraphs: instead of connecting pairs of terminals, we must connect sets of terminals. We give almost-complete dichotomies of the computational complexity of both problems for H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. Finally, we give a complete classification of the complexity of the second problem if the number k of terminal sets is fixed, that is, not part of the input.

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
¥17,985 /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
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 8464
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 10581
Price includes VAT (Japan)
  • 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. Belmonte, R., Golovach, P.A., Heggernes, P., van’t Hof, P., Kaminski, M., Paulusma, D.: Detecting fixed patterns in chordal graphs in polynomial time. Algorithmica 69, 501–521 (2014)

    Google Scholar 

  2. Bienstock, D.: On the complexity of testing for odd holes and induced odd paths. Discret. Math. 90, 85–92 (1991)

    Article  MathSciNet  Google Scholar 

  3. Brandstädt, A., Hoàng, C.T.: On clique separators, nearly chordal graphs, and the maximum weight stable set problem. Theoret. Comput. Sci. 389, 295–306 (2007)

    Article  MathSciNet  Google Scholar 

  4. Camby, E., Schaudt, O.: A new characterization of \({P}_k\)-free graphs. Algorithmica 75, 205–217 (2016)

    Article  MathSciNet  Google Scholar 

  5. Fellows, M.R.: The Robertson-Seymour theorems: a survey of applications. Proc. AMS-IMS-SIAM Joint Summer Res. Conf. Contemp. Math. 89, 1–18 (1989)

    Google Scholar 

  6. Fiala, J., Kamiński, M., Lidický, B., Paulusma, D.: The \(k\)-in-a-Path problem for claw-free graphs. Algorithmica 62, 499–519 (2012)

    Article  MathSciNet  Google Scholar 

  7. Gartland, P., Lokshtanov, D.: Independent set on \({P}_k\)-free graphs in quasi-polynomial time. In: Proceedings of the FOCS 2020, pp. 613–624 (2020)

    Google Scholar 

  8. Gartland, P., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Rzążewski, P.: Finding large induced sparse subgraphs in \({C}_{\>t}\)-free graphs in quasipolynomial time. In: Proceedings of the STOC 2021, pp. 330–341 (2021)

    Google Scholar 

  9. Golovach, P.A., Paulusma, D., van Leeuwen, E.J.: Induced disjoint paths in claw-free graphs. SIAM J. Discret. Math. 29, 348–375 (2015)

    Article  MathSciNet  Google Scholar 

  10. Golovach, P.A., Paulusma, D., van Leeuwen, E.J.: Induced disjoint paths in circular-arc graphs in linear time. Theoret. Comput. Sci. 640, 70–83 (2016)

    Article  MathSciNet  Google Scholar 

  11. Golovach, P.A., Paulusma, D., van Leeuwen, E.J.: Induced disjoint paths in AT-free graphs. J. Comput. Syst. Sci. 124, 170–191 (2022)

    Article  MathSciNet  Google Scholar 

  12. Grzesik, A., Klimosová, 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 

  13. van’t Hof, P., Paulusma, D.: A new characterization of \({P}_6\)-free graphs. Discrete Appl. Math. 158, 731–740 (2010)

    Google Scholar 

  14. van’t Hof, P., Paulusma, D., Woeginger, G.J.: Partitioning graphs into connected parts. Theoret. Comput. Sci. 410, 4834–4843 (2009)

    Google Scholar 

  15. Jaffke, L., Kwon, O., Telle, J.A.: Mim-width I. induced path problems. Discrete Appl. Math. 278, 153–168 (2020)

    Google Scholar 

  16. 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 

  17. Kawarabayashi, K., Kobayashi, Y.: A linear time algorithm for the induced disjoint paths problem in planar graphs. J. Comput. Syst. Sci. 78, 670–680 (2012)

    Article  MathSciNet  Google Scholar 

  18. Kern, W., Martin, B., Paulusma, D., Smith, S., van Leeuwen, E.J.: Disjoint paths and connected subgraphs for \(H\)-free graphs. Theoret. Comput. Sci. 898, 59–68 (2022)

    Article  MathSciNet  Google Scholar 

  19. Kern, W., Paulusma, D.: Contracting to a longest path in \({H}\)-free graphs. Proc. ISAAC 2020, LIPIcs 181, 22:1–22:18 (2020)

    Google Scholar 

  20. Kobayashi, Y., Kawarabayashi, K.: Algorithms for finding an induced cycle in planar graphs and bounded genus graphs. In: Proceedings of the SODA 2009, pp. 1146–1155 (2009)

    Google Scholar 

  21. Lévêque, B., Lin, D.Y., Maffray, F., Trotignon, N.: Detecting induced subgraphs. Discret. Appl. Math. 157, 3540–3551 (2009)

    Article  MathSciNet  Google Scholar 

  22. Li, W.N.: Two-segmented channel routing is strong NP-complete. Discret. Appl. Math. 78, 291–298 (1997)

    Article  MathSciNet  Google Scholar 

  23. Lynch, J.: The equivalence of theorem proving and the interconnection problem. SIGDA Newsl. 5, 31–36 (1975)

    Article  Google Scholar 

  24. Martin, B., Paulusma, D., Smith, S., van Leeuwen, E.J.: Few induced disjoint paths for \({H}\)-free graphs. Proc. ISCO 2022, LNCS (to appear)

    Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  26. Paesani, G., Paulusma, D., Rzążewski, P.: Feedback Vertex Set and Even Cycle Transversal for \({H}\)-free graphs: finding large block graphs. SIAM J. Discret. Math. (to appear)

    Google Scholar 

  27. Pilipczuk, M., Pilipczuk, M., Rzążewski, P.: Quasi-polynomial-time algorithm for independent set in \({P}_t\)-free graphs via shrinking the space of induced paths. In: Proceedings of the SOSA 2021, pp. 204–209 (2021)

    Google Scholar 

  28. Radovanović, M., Trotignon, N., Vus̆ković, K.: The (theta, wheel)-free graphs Part IV: induced paths and cycles. J. Comb. Theor. Ser. B 146, 495–531 (2021)

    Google Scholar 

  29. Robertson, N., Seymour, P.D.: Graph minors. XIII. The disjoint paths problem. J. Comb. Theor. Ser. B 63, 65–110 (1995)

    Google Scholar 

  30. Schaefer, T.J.: The complexity of satisfiability problems. In: STOC, pp. 216–226 (1978)

    Google Scholar 

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

    Article  Google Scholar 

Download references

Acknowledgments

We thank Paweł Rzążewski for the argument using blob graphs, which simplified two of our proofs and led to the case \(H=P_6\) in Theorem 1.

Author information

Authors and Affiliations

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

    Barnaby Martin, Daniël Paulusma & Siani Smith

  2. Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands

    Erik Jan van Leeuwen

Authors
  1. Barnaby Martin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Daniël Paulusma
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Siani Smith
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Erik Jan van Leeuwen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Siani Smith .

Editor information

Editors and Affiliations

  1. University of Ioannina, Ioannina, Greece

    Michael A. Bekos

  2. Universität Tübingen, Tübingen, Germany

    Michael Kaufmann

Rights and permissions

Reprints and permissions

Copyright information

© 2022 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Martin, B., Paulusma, D., Smith, S., van Leeuwen, E.J. (2022). Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. In: Bekos, M.A., Kaufmann, M. (eds) Graph-Theoretic Concepts in Computer Science. WG 2022. Lecture Notes in Computer Science, vol 13453. Springer, Cham. https://doi.org/10.1007/978-3-031-15914-5_29

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-15914-5_29

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-15913-8

  • Online ISBN: 978-3-031-15914-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation