Golovach, P.A. and Paulusma, Daniel and van Leeuwen, E.J. (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. Berlin ; Heidelberg: Springer, pp. 153-164. Lecture notes in computer science. (7357).
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-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.
|Item Type:||Book chapter|
|Full text:||Full text not available from this repository.|
|Publisher Web site:||http://dx.doi.org/10.1007/978-3-642-31155-0_14|
|Date accepted:||No date available|
|Date deposited:||No date available|
|Date of first online publication:||2012|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|