![](https://d3ilqtpdwi981i.cloudfront.net/3nVY74Fz0DvJuOu7PFg9agE7pmQ=/425x550/smart/https://bepress-attached-resources.s3.amazonaws.com/uploads/46/54/fe/4654fef9-18db-449f-9aa6-e0fc46eb59a4/thumbnail_5b8f1f26-3311-48cc-9897-8884680cb699.jpg)
Article
The k-in-a-Path Problem for Claw-free Graphs
Algorithmica
(2012)
Abstract
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 (si,ti) for i=1,…,k and is to test whether G contain k mutually induced paths Pi such that Pi connects si and ti 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.
Keywords
- Induced path,
- Claw-free graph,
- Polynomial time algorithm
Disciplines
Publication Date
February, 2012
DOI
10.1007/s00453-010-9468-z
Publisher Statement
The final publication is available at Springer via https://doi.org/10.1007/s00453-010-9468-z. Fiala, Jiří, Marcin Kamiński, Bernard Lidický, and Daniël Paulusma. "The k-in-a-path problem for claw-free graphs." Algorithmica 62, no. 1 (2012): 499-519.. doi: 10.1007/s00453-010-9468-z. Posted with permission
Copyright 2010 Springer Science+Business Media, LLC.
Citation Information
Jiří Fiala, Marcin Kamiński, Bernard Lidicky and Daniël Paulusma. "The k-in-a-Path Problem for Claw-free Graphs" Algorithmica Vol. 62 Iss. 1-2 (2012) p. 499 - 519 Available at: http://works.bepress.com/bernard-lidicky/22/