Contracting to a longest path in H-free graphs

Kern, W.; Paulusma, D.

doi:10.4230/lipics.isaac.2020.22

Contracting to a longest path in H-free graphs

Kern, W.; Paulusma, D.

Authors

W. Kern

Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor

Contributors

Y. Cao
Editor

Dr Sunny Cheng ting-yun.cheng@durham.ac.uk
Editor

M. Li
Editor

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). Contracting to a longest path in H-free graphs. In Y. Cao, S. Cheng, & M. Li (Eds.), 31st International Symposium on Algorithms and Computation (ISAAC 2020) (22:1-22:18). https://doi.org/10.4230/lipics.isaac.2020.22

Conference Name	ISAAC 2020
Conference Location	Hong Kong, China
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