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

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

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, December). The k-in-a-path problem for claw-free graphs. Presented at 27th International Symposium on Theoretical Aspects of Computer Science, Nancy, France

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 27th International Symposium on Theoretical Aspects of Computer Science
• Publication Date: Jan 1, 2010
• Deposit Date: Oct 6, 2010
• Publicly Available Date: Oct 7, 2010
• 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