The k‐in‐a‐Path Problem for Claw‐free Graphs

The k‐in‐a‐Path Problem for Claw‐free Graphs

0.00 Avg rating0 Votes
Article ID: iaor2012401
Volume: 62
Issue: 1
Start Page Number: 499
End Page Number: 519
Publication Date: Feb 2012
Journal: Algorithmica
Authors: , , ,
Keywords: minimum spanning trees, NP-complete, shortest path
Abstract:

The kin‐a‐Path problem is to test whether a graph contains an induced path spanning k given vertices. This problem is NP‐complete in general graphs, already when k=3. We show how to solve it in polynomial time on claw‐free graphs, when k is an arbitrary fixed integer not part of the input. As a consequence, also the kInduced Disjoint Paths and the kin‐a‐Cycle problem are solvable in polynomial time on claw‐free graphs for any fixed k. The first problem has as input a graph G and k pairs of specified vertices (s i ,t i ) for i=1,…,k and is to test whether G contain k mutually induced paths P i such that P i connects s i and t i for i=1,…,k. The second problem is to test whether a graph contains an induced cycle spanning k given vertices. When k is part of the input, we show that all three problems are NP‐complete, even for the class of line graphs, which form a subclass of the class of claw‐free graphs.

Reviews

Required fields are marked *. Your email address will not be published.