We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Finding induced paths of given parity in claw-free graphs.

Hof van 't, P. and Kamiński, M. and Paulusma, Daniel (2012) 'Finding induced paths of given parity in claw-free graphs.', Algorithmica., 62 (1-2). pp. 537-563.


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 O(n5)(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)(n5) time and O(n7)(n7) time, respectively. We also show that we can decide in O(n7)(n7) 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 O(n7)(n7) time.

Item Type:Article
Keywords:Induced path, Parity path, Claw-free graph, Polynomial-time algorithm.
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:The final publication is available at Springer via
Date accepted:No date available
Date deposited:16 January 2015
Date of first online publication:2012
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar