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

Fiala, J.; Kamiński, M.; Lidický, B.; Paulusma, D.

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 (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.

Citation

Fiala, J., Kamiński, M., Lidický, B., & Paulusma, D. (2012). The k-in-a-path problem for claw-free graphs. Algorithmica, 62(1-2), 499-519. https://doi.org/10.1007/s00453-010-9468-z

• Journal Article Type: Article
• Publication Date: Feb 1, 2012
• Deposit Date: Dec 6, 2011
• Publicly Available Date: Jan 16, 2015
• Journal: Algorithmica
• Print ISSN: 0178-4617
• Electronic ISSN: 1432-0541
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Volume: 62
• Issue: 1-2
• Pages: 499-519
• DOI: https://doi.org/10.1007/s00453-010-9468-z
• Keywords: Induced path, Claw-free graph, Polynomial time algorithm.
• Public URL: https://durham-repository.worktribe.com/output/1501899