Skip to main content

Research Repository

Advanced Search

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

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

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


Authors

J. Fiala

M. Kamiński

B. Lidický



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 Mar 28, 2024
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

Files





You might also like



Downloadable Citations