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.
|Keywords:||Induced path, Claw-free graph, Polynomial time algorithm.|
|Full text:||(AM) Accepted Manuscript|
Download PDF (311Kb)
|Publisher Web site:||http://dx.doi.org/10.1007/s00453-010-9468-z|
|Publisher statement:||The final publication is available at Springer via http://dx.doi.org/10.1007/s00453-010-9468-z|
|Record Created:||07 Dec 2011 14:35|
|Last Modified:||12 Aug 2015 16:28|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Look up in GoogleScholar | Find in a UK Library|