Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Hardness of approximation for H-Free edge modification problems. / Bliznets, Ivan; Cygan, Marek; Komosa, Paweł; Pilipczuk, Michał.
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016. ed. / Klaus Jansen; Claire Mathieu; Jose D. P. Rolim; Chris Umans. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016. (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 60).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
TY - GEN
T1 - Hardness of approximation for H-Free edge modification problems
AU - Bliznets, Ivan
AU - Cygan, Marek
AU - Komosa, Paweł
AU - Pilipczuk, Michał
PY - 2016/9/1
Y1 - 2016/9/1
N2 - The H-free 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 H-free, that is, not containing H as an induced subgraph. The H-free 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 H-free graphs exhibits some structural properties. In this work we complement the parameterized study of edge modification problems to H-free graphs by considering their approximability. We prove that whenever H is 3-connected and has at least two non-edges, then both H-free Edge Deletion and H-free 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 non-edges appears to be important: we show that whenever H is a complete graph without one edge, then H-free Edge Deletion is tightly connected to the Min Horn Deletion problem, whose approximability is still open. Finally, in an attempt to extend our hardness results beyond 3-connected graphs, we consider the cases of H being a path or a cycle, and we achieve an almost complete dichotomy there.
AB - The H-free 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 H-free, that is, not containing H as an induced subgraph. The H-free 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 H-free graphs exhibits some structural properties. In this work we complement the parameterized study of edge modification problems to H-free graphs by considering their approximability. We prove that whenever H is 3-connected and has at least two non-edges, then both H-free Edge Deletion and H-free 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 non-edges appears to be important: we show that whenever H is a complete graph without one edge, then H-free Edge Deletion is tightly connected to the Min Horn Deletion problem, whose approximability is still open. Finally, in an attempt to extend our hardness results beyond 3-connected graphs, we consider the cases of H being a path or a cycle, and we achieve an almost complete dichotomy there.
KW - Edge Modification Problems
KW - Hardness Of Approximation
KW - Kernelization
KW - Parameterized Complexity
UR - http://www.scopus.com/inward/record.url?scp=84990866126&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.APPROX-RANDOM.2016.3
DO - 10.4230/LIPIcs.APPROX-RANDOM.2016.3
M3 - Conference contribution
AN - SCOPUS:84990866126
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016
A2 - Jansen, Klaus
A2 - Mathieu, Claire
A2 - Rolim, Jose D. P.
A2 - Umans, Chris
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2016 and the 20th International Workshop on Randomization and Computation, RANDOM 2016
Y2 - 7 September 2016 through 9 September 2016
ER -
ID: 49787328