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:

The k-in-a-path problem for claw-free graphs.

Fiala, J. and Kaminski, M. and Lidický, B. and Paulusma, Daniel (2012) 'The k-in-a-path problem for claw-free graphs.', Algorithmica., 62 (1-2). pp. 499-519.


The k-in-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 k-Induced Disjoint Paths and the k-in-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.

Item Type:Article
Keywords:Induced path, Claw-free graph, Polynomial time algorithm.
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:The final publication is available at Springer via
Date accepted:No date available
Date deposited:16 January 2015
Date of first online publication:February 2012
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar