[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content

Induced Disjoint Paths in AT-Free Graphs

  • Conference paper
Algorithm Theory – SWAT 2012 (SWAT 2012)

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

Included in the following conference series:

Abstract

Paths P 1,…,P k in a graph G = (V,E) are said to be mutually induced if for any 1 ≤ i < j ≤ k, P i and P j have neither common vertices nor adjacent vertices (except perhaps their end-vertices). The Induced Disjoint Paths problem is to test whether a graph G with k pairs of specified vertices (s i ,t i ) contains k mutually induced paths P i such that P i connects s i and t i for i = 1,…,k. This problem is known to be NP-complete already for k = 2. We prove that it can be solved in polynomial time for AT-free graphs even when k is part of the input. As a consequence, the problem of testing whether a given AT-free graph contains some graph H as an induced topological minor admits a polynomial-time algorithm, as long as H is fixed; we show that such an algorithm is essentially optimal by proving that the problem is W[1]-hard, even on a subclass of AT-free graphs, namely cobipartite graphs, when parameterized by |V H |. We also show that the problems k -in-a-Path and k -in-a-Tree can be solved in polynomial time, even when k is part of the input. These problems are to test whether a graph contains an induced path or induced tree, respectively, spanning k given vertices.

This work is supported by EPSRC (EP/G043434/1), Royal Society (JP100692), and ERC StG project PAAl no. 259515.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
£29.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
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 35.99
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 44.99
Price includes VAT (United Kingdom)
  • 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

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Belmonte, R., Golovach, P.A., Heggernes, P.: van’t Hof, P., Kaminski, M., Paulusma, D.: Detecting patterns in chordal graphs (preprint)

    Google Scholar 

  2. Bienstock, D.: On the complexity of testing for odd holes and induced odd paths. Disc. Math. 90, 85–92 (1991); See also Corrigendum. Disc. Math. 102, 109 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  3. Broersma, H.J., Kloks, T., Kratsch, D., Müller, H.: Independent Sets in Asteroidal Triple-Free Graphs. SIAM J. Discrete Math. 12, 276–287 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  4. Chudnovsky, M., Seymour, P.D.: The three-in-a-tree problem. Combinatorica 30, 387–417 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  5. Derhy, N., Picouleau, C.: Finding induced trees. Discrete Applied Mathematics 157, 3552–3557 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  6. Corneil, D.G., Olariu, S., Stewart, L.: Asteroidal Triple-Free Graphs. SIAM J. Discrete Math. 10, 299–430 (1997)

    Article  MathSciNet  Google Scholar 

  7. Corneil, D.G., Olariu, S., Stewart, L.: Linear time algorithms for dominating pairs in asteroidal triple-free graphs. SIAM J. Comput. 28, 1284–1297 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  8. Downey, R.G., Fellows, M.R.: Parameterized complexity. Monographs in Computer Science. Springer, New York (1999)

    Book  Google Scholar 

  9. Fellows, M.R.: The Robertson-Seymour theorems: A survey of applications. In: Richter, R.B. (ed.) Proc. AMS-IMS-SIAM Joint Summer Research Conference. Contemporary Mathematics, vol. 89, pp. 1–18. Amer. Math. Soc., Providence (1989)

    Google Scholar 

  10. Fiala, J., Kamiński, M., Lidicky, B., Paulusma, D.: The k-in-a-path problem for claw-free graphs. Algorithmica 62, 499–519 (2012)

    Article  MATH  Google Scholar 

  11. Golovach, P.A., Paulusma, D., van Leeuwen, E.J.: Induced Disjoint Paths in Claw-Free Graphs. arXiv:1202.4419v1 [cs.DM] (2012)

    Google Scholar 

  12. Grohe, M., Kawarabayashi, K., Marx, D., Wollan, P.: Finding topological subgraphs is fixed-parameter tractable. In: Proc. STOC, pp. 479–488 (2011)

    Google Scholar 

  13. Karp, R.M.: On the complexity of combinatorial problems. Networks 5, 45–68 (1975)

    MathSciNet  MATH  Google Scholar 

  14. Kloks, T., Kratsch, D., Müller, H.: On the structure of graphs with bounded asteroidal number. Graphs and Combinatorics 17, 295–306 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  15. Kobayashi, Y., Kawarabayashi, K.: A linear time algorithm for the induced disjoint paths problem in planar graphs. JCSS 78, 670–680 (2012)

    MATH  Google Scholar 

  16. Kratsch, D.: Domination and total domination on asteroidal triple-free graphs. Discrete Applied Mathematics 99, 111–123 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  17. Kratsch, D., Müller, H., Todinca, I.: Feedback Vertex Set and Longest Induced Path on AT-Free Graphs. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol. 2880, pp. 309–321. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  18. Lekkerkerker, C.G., Boland, J.C.: Representation of a finite graph by a set of intervals on the real line. Fund. Math. 51, 45–64

    Google Scholar 

  19. Lévêque, B., Lin, D.Y., Maffray, F., Trotignon, N.: Detecting induced subgraphs. Discrete Applied Mathematics 157, 3540–3551 (2009)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  Google Scholar 

  21. McDiarmid, C.J.H., Reed, B.A., Schrijver, A., Shepherd, F.B.: Induced Circuits in Planar Graphs. J. Comb. Theory B 60, 169–176 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  22. Natarajan, S., Sprague, A.P.: Disjoint Paths in Circular Arc Graphs. Nord. J. Comput. 3, 256–270 (1996)

    MathSciNet  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  24. Stacho, J.: 3-Colouring AT-Free Graphs in Polynomial Time. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010, Part II. LNCS, vol. 6507, pp. 144–155. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2012 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Golovach, P.A., Paulusma, D., van Leeuwen, E.J. (2012). Induced Disjoint Paths in AT-Free Graphs. In: Fomin, F.V., Kaski, P. (eds) Algorithm Theory – SWAT 2012. SWAT 2012. Lecture Notes in Computer Science, vol 7357. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31155-0_14

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-31155-0_14

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-31154-3

  • Online ISBN: 978-3-642-31155-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics