License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2022.24
URN: urn:nbn:de:0030-drops-173097
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17309/
Go to the corresponding LIPIcs Volume Portal

Belova, Tatiana ; Bliznets, Ivan

Hardness of Approximation for H-Free Edge Modification Problems: Towards a Dichotomy

pdf-format:
LIPIcs-ISAAC-2022-24.pdf (0.7 MB)

Abstract

For a fixed graph H, the H-free Edge Deletion/Completion/Editing problem asks to delete/add/edit the minimum possible number of edges in G to get a graph that does not contain an induced subgraph isomorphic to the graph H. In this work, we investigate H-free Edge Deletion/Completion/Editing problems in terms of the hardness of their approximation. We formulate a conjecture according to which all the graphs with at least five vertices can be classified into several groups of graphs with specific structural properties depending on the hardness of approximation for the corresponding H-free Edge Deletion/Completion/Editing problems. Also, we make significant progress in proving that conjecture by showing that it is sufficient to resolve it only for a finite set of graphs.

BibTeX - Entry

@InProceedings{belova_et_al:LIPIcs.ISAAC.2022.24,
  author =	{Belova, Tatiana and Bliznets, Ivan},
  title =	{{Hardness of Approximation for H-Free Edge Modification Problems: Towards a Dichotomy}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{24:1--24:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17309},
  URN =		{urn:nbn:de:0030-drops-173097},
  doi =		{10.4230/LIPIcs.ISAAC.2022.24},
  annote =	{Keywords: Parameterized complexity, Hardness of approximation, Edge modification problems}
}

Keywords: Parameterized complexity, Hardness of approximation, Edge modification problems
Collection: 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Issue Date: 2022
Date of publication: 14.12.2022

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