License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2020.22
URN: urn:nbn:de:0030-drops-133664
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13366/
Go to the corresponding LIPIcs Volume Portal

Kern, Walter ; Paulusma, Daniël

Contracting to a Longest Path in H-Free Graphs

pdf-format:
LIPIcs-ISAAC-2020-22.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{kern_et_al:LIPIcs:2020:13366,
  author =	{Walter Kern and Dani{\"e}l Paulusma},
  title =	{{Contracting to a Longest Path in H-Free Graphs}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{22:1--22:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Yixin Cao and Siu-Wing Cheng and Minming Li},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13366},
  URN =		{urn:nbn:de:0030-drops-133664},
  doi =		{10.4230/LIPIcs.ISAAC.2020.22},
  annote =	{Keywords: dichotomy, edge contraction, path, cycle, H-free graph}
}

Keywords: dichotomy, edge contraction, path, cycle, H-free graph
Collection: 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Issue Date: 2020
Date of publication: 04.12.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI