Kern, Walter ;
Paulusma, Daniël
Contracting to a Longest Path in HFree Graphs
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 kvertex path P_k by a sequence of edge contractions. A graph G is Hfree for some graph H if G does not contain H as an induced subgraph. The Path Contraction problem restricted to Hfree graphs is known to be NPcomplete if H = claw or H = P₆ and polynomialtime solvable if H = P₅. We first settle the complexity of Path Contraction on Hfree 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 Hfree graphs do not coincide. The latter problem, which has not been fully classified for Hfree graphs yet, is to decide if for some given integer k, a given graph contains the kvertex cycle C_k as a contraction.
BibTeX  Entry
@InProceedings{kern_et_al:LIPIcs:2020:13366,
author = {Walter Kern and Dani{\"e}l Paulusma},
title = {{Contracting to a Longest Path in HFree Graphs}},
booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)},
pages = {22:122:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771733},
ISSN = {18688969},
year = {2020},
volume = {181},
editor = {Yixin Cao and SiuWing Cheng and Minming Li},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13366},
URN = {urn:nbn:de:0030drops133664},
doi = {10.4230/LIPIcs.ISAAC.2020.22},
annote = {Keywords: dichotomy, edge contraction, path, cycle, Hfree graph}
}
04.12.2020
Keywords: 

dichotomy, edge contraction, path, cycle, Hfree graph 
Seminar: 

31st International Symposium on Algorithms and Computation (ISAAC 2020)

Issue date: 

2020 
Date of publication: 

04.12.2020 