Contracting to a longest path in H-free graphs

Kern, W.; Paulusma, D.

Abstract

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.

Citation

Kern, W., & Paulusma, D. (2020, December). Contracting to a longest path in H-free graphs. Presented at ISAAC 2020, Hong Kong, China

• Presentation Conference Type: Conference Paper (published)
• Conference Name: ISAAC 2020
• Acceptance Date: Aug 31, 2020
• Online Publication Date: Dec 4, 2020
• Publication Date: 2020
• Deposit Date: Sep 1, 2020
• Publicly Available Date: Jan 21, 2021
• Volume: 181
• Pages: 22:1-22:18
• Series Title: Leibniz International Proceedings in Informatics
• Series Number: 22
• Book Title: 31st International Symposium on Algorithms and Computation (ISAAC 2020)
• DOI: https://doi.org/10.4230/lipics.isaac.2020.22
• Public URL: https://durham-repository.worktribe.com/output/1140847