Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Induced disjoint paths in AT-free graphs.

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

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.

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

Export:
Export
Look up in GoogleScholar