Induced Disjoint Paths in Claw-Free Graphs

Details Induced Disjoint Paths in Claw-Free Graphs Induced Disjoint Paths in Claw-Free Graphs

2012-02-20

arxiv.org/abs/1202.4419v1

Computer Science

Discrete Mathematics

Scientific paper

Paths P_1, ..., P_k in a graph G=(V, E) are said to be mutually induced if for any 1 <= i < j <= k, P_i and P_j 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 (s_i, t_i) contains k mutually induced paths P_i such that P_i connects s_i and t_i 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 n^O(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 also show that an improvement of these results in certain directions is unlikely, for example by observing that the Induced Disjoint Paths problem cannot have a polynomial kernel for line graphs (a type of claw-free graphs), unless NP \subseteq coNP/poly. Moreover, the problem becomes NP-complete, even when k=2, for the more general class of K_{1,4}-free graphs. Finally, we show that the n^O(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.

Affiliated with

Also associated with

No associations

Rating

Induced Disjoint Paths in Claw-Free Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Induced Disjoint Paths in Claw-Free Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Induced Disjoint Paths in Claw-Free Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-565667