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 (720Kb)
|Publisher Web site:||https://doi.org/10.4230/LIPIcs.ISAAC.2020.22|
|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|