Skip to main content

Research Repository

Advanced Search

Induced disjoint paths in AT-free graphs

Golovach, P. A.; Paulusma, D.; van Leeuwen, E. J.

Authors

P. A. Golovach

E. J. van Leeuwen



Contributors

Fedor V. Fomin
Editor

Petteri Kaski
Editor

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. A., Paulusma, D., & van Leeuwen, E. J. (2012). Induced disjoint paths in AT-free graphs. In F. V. Fomin, & P. Kaski (Eds.), 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
Public URL https://durham-repository.worktribe.com/output/1156971
Additional Information Series: Lecture Notes in Computer Science, Volume 7357


You might also like



Downloadable Citations