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:

Contracting to a longest path in H-free graphs

Kern, W. and Paulusma, D. (2020) 'Contracting to a longest path in H-free graphs.', in 31st International Symposium on Algorithms and Computation (ISAAC 2020). , 22:1-22:18. Leibniz International Proceedings in Informatics., 181


The Path Contraction problem has as input a graph G and an integer k and is to decide if G can be modified to the k-vertex path P_k by a sequence of edge contractions. A graph G is H-free for some graph H if G does not contain H as an induced subgraph. The Path Contraction problem restricted to H-free graphs is known to be NP-complete if H = claw or H = P₆ and polynomial-time solvable if H = P₅. We first settle the complexity of Path Contraction on H-free graphs for every H by developing a common technique. We then compare our classification with a (new) classification of the complexity of the problem Long Induced Path, which is to decide for a given integer k, if a given graph can be modified to P_k by a sequence of vertex deletions. Finally, we prove that the complexity classifications of Path Contraction and Cycle Contraction for H-free graphs do not coincide. The latter problem, which has not been fully classified for H-free graphs yet, is to decide if for some given integer k, a given graph contains the k-vertex cycle C_k as a contraction.

Item Type:Book chapter
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution 3.0.
Download PDF
Publisher Web site:
Publisher statement:© Walter Kern and Daniël Paulusma; licensed under Creative Commons License CC-BY
Date accepted:31 August 2020
Date deposited:21 January 2021
Date of first online publication:04 December 2020
Date first made open access:21 January 2021

Save or Share this output

Look up in GoogleScholar