@online{Marx_arXiv2004.11761,
TITLE = {Incompressibility of H-free Edge Modification Problems: Towards a Dichotomy},
AUTHOR = {Marx, D{\'a}niel and Sandeep, R. B.},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2004.11761},
EPRINT = {2004.11761},
EPRINTTYPE = {arXiv},
YEAR = {2020},
ABSTRACT = {Given a graph $G$ and an integer $k$, the $H$-free Edge Editing problem is to<br>find whether there exists at most $k$ pairs of vertices in $G$ such that<br>changing the adjacency of the pairs in $G$ results in a graph without any<br>induced copy of $H$. The existence of polynomial kernels for $H$-free Edge<br>Editing received significant attention in the parameterized complexity<br>literature. Nontrivial polynomial kernels are known to exist for some graphs<br>$H$ with at most 4 vertices, but starting from 5 vertices, polynomial kernels<br>are known only if $H$ is either complete or empty. This suggests the conjecture<br>that there is no other $H$ with at least 5 vertices were $H$-free Edge Editing<br>admits a polynomial kernel. Towards this goal, we obtain a set $\mathcal{H}$ of<br>nine 5-vertex graphs such that if for every $H\in\mathcal{H}$, $H$-free Edge<br>Editing is incompressible and the complexity assumption $NP \not\subseteq<br>coNP/poly$ holds, then $H$-free Edge Editing is incompressible for every graph<br>$H$ with at least five vertices that is neither complete nor empty. That is,<br>proving incompressibility for these nine graphs would give a complete<br>classification of the kernelization complexity of $H$-free Edge Editing for<br>every $H$ with at least 5 vertices.<br> We obtain similar result also for $H$-free Edge Deletion. Here the picture is<br>more complicated due to the existence of another infinite family of graphs $H$<br>where the problem is trivial (graphs with exactly one edge). We obtain a larger<br>set $\mathcal{H}$ of nineteen graphs whose incompressibility would give a<br>complete classification of the kernelization complexity of $H$-free Edge<br>Deletion for every graph $H$ with at least 5 vertices. Analogous results follow<br>also for the $H$-free Edge Completion problem by simple complementation.<br>},
}