Induced disjoint paths in claw-free graphs

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

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

Citation

Golovach, P. A., Paulusma, D., & van Leeuwen, E. J. (2012, December). Induced disjoint paths in claw-free graphs

• Presentation Conference Type: Conference Paper (published)
• Publication Date: 2012
• Deposit Date: Mar 11, 2013
• Print ISSN: 0302-9743
• Pages: 515-526
• Series Title: Lecture notes in computer science
• Series Number: 7501
• Series ISSN: 0302-9743,1611-3349
• Book Title: Algorithms, 20th Annual European Symposium, ESA 2012, Ljubljana, Slovenia, 10-12 September 2012 ; proceedings.
• ISBN: 9783642330896
• DOI: https://doi.org/10.1007/978-3-642-33090-2_45
• Public URL: https://durham-repository.worktribe.com/output/1157000
• Additional Information: Series: Lecture Notes in Computer Science, Volume 7501