Marx, Dániel ;
Sandeep, R. B.
Incompressibility of HFree Edge Modification Problems: Towards a Dichotomy
Abstract
Given a graph G and an integer k, the Hfree Edge Editing problem is to find whether there exist at most k pairs of vertices in G such that changing the adjacency of the pairs in G results in a graph without any induced copy of H. The existence of polynomial kernels for Hfree Edge Editing (that is, whether it is possible to reduce the size of the instance to k^O(1) in polynomial time) received significant attention in the parameterized complexity literature. Nontrivial polynomial kernels are known to exist for some graphs H with at most 4 vertices (e.g., path on 3 or 4 vertices, diamond, paw), but starting from 5 vertices, polynomial kernels are known only if H is either complete or empty. This suggests the conjecture that there is no other H with at least 5 vertices were Hfree Edge Editing admits a polynomial kernel. Towards this goal, we obtain a set ℋ of nine 5vertex graphs such that if for every H ∈ ℋ, Hfree Edge Editing is incompressible and the complexity assumption NP ⊈ coNP/poly holds, then Hfree Edge Editing is incompressible for every graph H with at least five vertices that is neither complete nor empty. That is, proving incompressibility for these nine graphs would give a complete classification of the kernelization complexity of Hfree Edge Editing for every H with at least 5 vertices.
We obtain similar result also for Hfree Edge Deletion. Here the picture is more complicated due to the existence of another infinite family of graphs H where the problem is trivial (graphs with exactly one edge). We obtain a larger set ℋ of nineteen graphs whose incompressibility would give a complete classification of the kernelization complexity of Hfree Edge Deletion for every graph H with at least 5 vertices. Analogous results follow also for the Hfree Edge Completion problem by simple complementation.
BibTeX  Entry
@InProceedings{marx_et_al:LIPIcs:2020:12938,
author = {D{\'a}niel Marx and R. B. Sandeep},
title = {{Incompressibility of HFree Edge Modification Problems: Towards a Dichotomy}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {72:172:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771627},
ISSN = {18688969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12938},
URN = {urn:nbn:de:0030drops129383},
doi = {10.4230/LIPIcs.ESA.2020.72},
annote = {Keywords: incompressibility, edge modification problems, Hfree graphs}
}
26.08.2020
Keywords: 

incompressibility, edge modification problems, Hfree graphs 
Seminar: 

28th Annual European Symposium on Algorithms (ESA 2020)

Issue date: 

2020 
Date of publication: 

26.08.2020 