Bliznets, Ivan ;
Cygan, Marek ;
Komosa, Pawel ;
Pilipczuk, Michal
Hardness of Approximation for HFree Edge Modification Problems
Abstract
The Hfree Edge Deletion problem asks, for a given graph G and integer k, whether it is possible to delete at most k edges from G to make it Hfree, that is, not containing H as an induced subgraph. The Hfree Edge Completion problem is defined similarly, but we add edges instead of deleting them. The study of these two problem families has recently been the subject of intensive studies from the point of view of parameterized complexity and kernelization. In particular, it was shown that the problems do not admit polynomial kernels (under plausible complexity assumptions) for almost all graphs H, with several important exceptions occurring when the class of Hfree graphs exhibits some structural properties.
In this work we complement the parameterized study of edge modification problems to Hfree graphs by considering their approximability. We prove that whenever H is 3connected and has at least two nonedges, then both Hfree Edge Deletion and Hfree Edge Completion are very hard to approximate: they do not admit poly(OPT)approximation in polynomial time, unless P=NP, or even in time subexponential in OPT, unless the Exponential Time Hypothesis fails. The assumption of the existence of two nonedges appears to be important: we show that whenever H is a complete graph without one edge, then Hfree Edge Deletion is tightly connected to the \minhorn problem, whose approximability is still open. Finally, in an attempt to extend our hardness results beyond 3connected graphs, we consider the cases of H being a path or a cycle, and we achieve an almost complete dichotomy there.
BibTeX  Entry
@InProceedings{bliznets_et_al:LIPIcs:2016:6626,
author = {Ivan Bliznets and Marek Cygan and Pawel Komosa and Michal Pilipczuk},
title = {{Hardness of Approximation for HFree Edge Modification Problems}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
pages = {3:13:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770187},
ISSN = {18688969},
year = {2016},
volume = {60},
editor = {Klaus Jansen and Claire Mathieu and Jos{\'e} D. P. Rolim and Chris Umans},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6626},
URN = {urn:nbn:de:0030drops66260},
doi = {10.4230/LIPIcs.APPROXRANDOM.2016.3},
annote = {Keywords: hardness of approximation, parameterized complexity, kernelization, edge modification problems}
}
2016
Keywords: 

hardness of approximation, parameterized complexity, kernelization, edge modification problems 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Issue date: 

2016 
Date of publication: 

2016 