The k-in-a-path Problem for Claw-free Graphs

Authors Jiri Fiala, Marcin Kaminski, Bernard Lidický, Daniël Paulusma



PDF
Thumbnail PDF

File

LIPIcs.STACS.2010.2469.pdf
  • Filesize: 304 kB
  • 12 pages

Document Identifiers

Author Details

Jiri Fiala
Marcin Kaminski
Bernard Lidický
Daniël Paulusma

Cite AsGet BibTex

Jiri Fiala, Marcin Kaminski, Bernard Lidický, and Daniël Paulusma. The k-in-a-path Problem for Claw-free Graphs. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 371-382, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
https://doi.org/10.4230/LIPIcs.STACS.2010.2469

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

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail