Finding induced paths of given parity in claw-free graphs

Pim van 't Hof, Marcin Kaminski, Daniël Paulusma

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)
3 Downloads (Pure)

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(n5) 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(n5) time and O(n7) time, respectively. We also show that we can decide in O(n7) time whether a claw-free graph has an induced cycle of given parity through a specified vertex.
Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science, 35th International Workshop, WG 2009, Montpellier, France, June 24-26, 2009. Revised Papers
EditorsChristophe Paul, Michel Habib
Pages341-352
Number of pages12
ISBN (Electronic)978-3-642-11409-0
DOIs
Publication statusPublished - 2009
Externally publishedYes
Event35th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2009 - Montpellier, France
Duration: 24 Jun 200926 Jun 2009
Conference number: 35

Publication series

NameLecture Notes in Computer Science
Volume5911

Conference

Conference35th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2009
Abbreviated titleWG
Country/TerritoryFrance
CityMontpellier
Period24/06/0926/06/09

Fingerprint

Dive into the research topics of 'Finding induced paths of given parity in claw-free graphs'. Together they form a unique fingerprint.

Cite this