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

Jiří Fiala; Marcin Kamiński; Bernard Lidický; Daniël Paulusma

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

Jiří Fiala ^{1, 2, *} Marcin Kamiński ³ Bernard Lidický ^{1, 2} Daniël Paulusma ⁴

* Corresponding author

1 ITI - Institute for Theoretical Computer Science

2 Faculty of Mathematics and Physics, DIMATIA

3 ULB - Computer Science Department [Bruxelles]

4 Department of Computer Science

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.

Keywords : induced path claw-free graph polynomial-time algorithm

Document type :

Conference papers

Domain :

Computer Science [cs] / Discrete Mathematics [cs.DM]

Computer Science [cs] / Data Structures and Algorithms [cs.DS]

Complete list of metadatas

Cited literature [20 references] Display Hide Download

https://hal.inria.fr/inria-00455353
Contributor : Publications Loria <>
Submitted on : Wednesday, February 10, 2010 - 11:00:13 AM
Last modification on : Thursday, July 19, 2018 - 4:58:09 PM
Long-term archiving on : Friday, June 18, 2010 - 6:13:21 PM

fiala.pdf

Files produced by the author(s)

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

File

Identifiers

Collections

Citation

Export

Metrics

184

128

Contact

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

File

Identifiers

Collections

Citation

Export

Share

Metrics

184

128

Contact