Skip to main content

Research Repository

Advanced Search

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

Fiala, J.; Kaminski, M.; Lidicky, B.; Paulusma, D.

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


Authors

J. Fiala

M. Kaminski

B. Lidicky



Contributors

Jean-Yves Marion
Editor

Thomas Schwentick
Editor

Abstract

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.

Citation

Fiala, J., Kaminski, M., Lidicky, B., & Paulusma, D. (2010). The k-in-a-path problem for claw-free graphs. In J. Marion, & T. Schwentick (Eds.), 27th International symposium on theoretical aspects of computer science, STACS 2010, 4-6 March 2010 ; proceedings (371-382). https://doi.org/10.4230/lipics.stacs.2010.2469

Conference Name 27th International Symposium on Theoretical Aspects of Computer Science
Conference Location Nancy, France
Publication Date Jan 1, 2010
Deposit Date Oct 6, 2010
Publicly Available Date Mar 29, 2024
Pages 371-382
Series Title Leibniz international proceedings in informatics
Series Number 5
Series ISSN 1868-8969
Book Title 27th International symposium on theoretical aspects of computer science, STACS 2010, 4-6 March 2010 ; proceedings.
ISBN 9783939897163
DOI https://doi.org/10.4230/lipics.stacs.2010.2469
Keywords Induced path, Claw-free graph, Polynomial-time algorithm.
Public URL https://durham-repository.worktribe.com/output/1159660

Files





You might also like



Downloadable Citations