Finding Induced Paths of Given Parity in Claw‐Free Graphs

Finding Induced Paths of Given Parity in Claw‐Free Graphs

0.00 Avg rating0 Votes
Article ID: iaor2012403
Volume: 62
Issue: 1
Start Page Number: 537
End Page Number: 563
Publication Date: Feb 2012
Journal: Algorithmica
Authors: , ,
Keywords: NP-complete, path planning, arc routing
Abstract:

The Parity Path problem is to decide if a given graph contains both an induced path of odd length and an induced path of even length between two specified vertices. 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 𝒪 ( n 5 ) equ1 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 𝒪 ( n 5 ) equ2 time and 𝒪 ( n 7 ) equ3 time, respectively. We also show that we can decide in 𝒪 ( n 7 ) equ4 time whether a claw‐free graph has an induced cycle of given parity through a specified vertex. Finally, we show that a shortest induced path of given parity between two specified vertices of a claw‐free perfect graph can be found in 𝒪 ( n 7 ) equ5 time.

Reviews

Required fields are marked *. Your email address will not be published.