We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham Research Online
You are in:

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

Fiala, J. and Kaminski, M. and Lidicky, 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:Full text not available from this repository.
Publisher Web site:
Record Created:07 Dec 2011 14:35
Last Modified:03 Apr 2013 16:22

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library