Induced disjoint paths in AT-free graphs

Golovach, P.A.; Paulusma, D.; van Leeuwen, E.J.; Fomin, Fedor V.; Kaski, Petteri

Abstract

Paths P1,…,Pk in a graph G = (V,E) are said to be mutually induced if for any 1 ≤ i < j ≤ k, Pi and Pj 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 (si,ti) contains k mutually induced paths Pi such that Pi connects si and ti 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 |VH|. 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.

Citation

Golovach, P., Paulusma, D., van Leeuwen, E., Fomin, F. V., & Kaski, P. (2012). Induced disjoint paths in AT-free graphs. In Algorithm Theory : 13th Scandinavian Symposium and Workshops, SWAT 2012, Helsinki, Finland, 4-6 July 2012 ; proceedings (153-164). https://doi.org/10.1007/978-3-642-31155-0_14

• Publication Date: 2012
• Deposit Date: Mar 11, 2013
• Pages: 153-164
• Series Title: Lecture notes in computer science
• Series Number: 7357
• Series ISSN: 0302-9743,1611-3349
• Book Title: Algorithm Theory : 13th Scandinavian Symposium and Workshops, SWAT 2012, Helsinki, Finland, 4-6 July 2012 ; proceedings.
• ISBN: 9783642311543
• DOI: https://doi.org/10.1007/978-3-642-31155-0_14
• Additional Information: Series: Lecture Notes in Computer Science, Volume 7357