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 Lidicky, B. and Paulusma, Daniel (2010) 'The k-in-a-path problem for claw-free graphs.', in 27th International symposium on theoretical aspects of computer science, STACS 2010, 4-6 March 2010 ; proceedings. Saarbrücken, Germany: Dagstuhl, 371-382 . Leibniz international proceedings in informatics. (5).


Testing whether there is an induced path in a graph spanning $k$ given vertices is already \NP-complete in general graphs when $k=3$. We show how to solve this problem in polynomial time on claw-free graphs, when $k$ is not part of the input but an arbitrarily fixed integer.

Item Type:Book chapter
Keywords:Induced path, Claw-free graph, Polynomial-time algorithm.
Full text:(VoR) Version of Record
Download PDF
Publisher Web site:
Publisher statement:This article is made available under a Creative Commons Attribution-No Derivative Works 3.0 Unported License.
Date accepted:No date available
Date deposited:07 October 2010
Date of first online publication:2010
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar