Skip to main content

Research Repository

Advanced Search

Finding Induced Paths of Given Parity in Claw-Free Graphs

Hof van 't, P.; Kaminski, M.; Paulusma, D.

Authors

P. Hof van 't

M. Kaminski



Contributors

C. Paul
Editor

M. Habib
Editor

Abstract

The Parity Path problem is to decide if a given graph G contains both an odd length and an even length induced path between two specified vertices s and t. In the related problems Odd Induced Path and Even Induced Path, the goal is to determine whether an induced path of odd, respectively even, length between two specified vertices exists. Although all three problems are NP-complete in general, we show that they can be solved in O(n^5) time for the class of claw-free graphs. Two vertices s and t form an even pair in G if every induced path from s to t in G has even length. Our results imply that the problem of deciding if two specified vertices of a claw-free graph form an even pair, as well as the problem of deciding if a given claw-free graph has an even pair, can be solved in O(n^5) time and O(n^7) time, respectively. We also show that we can decide in O(n^7) time whether a claw-free graph has an induced cycle of given parity through a specified vertex.

Citation

Hof van 't, P., Kaminski, M., & Paulusma, D. (2009). Finding Induced Paths of Given Parity in Claw-Free Graphs. In C. Paul, & M. Habib (Eds.), Graph-theoretic concepts in computer science (341-352). https://doi.org/10.1007/978-3-642-11409-0_30

Conference Name 35th International Workshop on Graph-Theoretic Concepts in Computer Science
Conference Location Montpellier, France
Publication Date Dec 1, 2009
Deposit Date Jan 5, 2010
Publisher Springer Verlag
Pages 341-352
Series Title Lecture notes in computer science
Series Number 5911
Book Title Graph-theoretic concepts in computer science.
DOI https://doi.org/10.1007/978-3-642-11409-0_30
Public URL https://durham-repository.worktribe.com/output/1160317


You might also like



Downloadable Citations