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 claw-free graphs.

Golovach, P.A. and Paulusma, Daniel and van Leeuwen, E.J. (2012) 'Induced disjoint paths in claw-free graphs.', in Algorithms, 20th Annual European Symposium, ESA 2012, Ljubljana, Slovenia, 10-12 September 2012 ; proceedings. Berlin ; Heidelberg: Springer, pp. 515-526. Lecture notes in computer science. (7501).


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, but for n-vertex claw-free graphs, Fiala et al.gave an nO(k)-time algorithm. We improve the latter result by showing that the problem is fixed-parameter tractable for claw-free graphs when parameterized by k. Several related problems, such as the k-in-a-Path problem, are shown to be fixed-parameter tractable for claw-free graphs as well. We prove that an improvement of these results in certain directions is unlikely, for example by noting that the Induced Disjoint Paths problem cannot have a polynomial kernel for line graphs (a type of claw-free graphs), unless NP ⊆ coNP/poly. Moreover, the problem becomes NP-complete, even when k = 2, for the more general class of K1,4-free graphs. Finally, we show that the nO(k)-time algorithm of Fiala et al.for testing whether a claw-free graph contains some k-vertex graph H as a topological induced minor is essentially optimal by proving that this problem is W[1]-hard even if G and H are line graphs.

Item Type:Book chapter
Full text:Full text not available from this repository.
Publisher Web site:
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