hide
Free keywords:
Computer Science, Data Structures and Algorithms, cs.DS
Abstract:
Given a graph $G$ and an integer $k$, the $H$-free Edge Editing problem is to
find whether there exists 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 $H$-free Edge
Editing received significant attention in the parameterized complexity
literature. Nontrivial polynomial kernels are known to exist for some graphs
$H$ with at most 4 vertices, 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 $H$-free Edge Editing
admits a polynomial kernel. Towards this goal, we obtain a set $\mathcal{H}$ of
nine 5-vertex graphs such that if for every $H\in\mathcal{H}$, $H$-free Edge
Editing is incompressible and the complexity assumption $NP \not\subseteq
coNP/poly$ holds, then $H$-free 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 $H$-free Edge Editing for
every $H$ with at least 5 vertices.
We obtain similar result also for $H$-free 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 $\mathcal{H}$ of nineteen graphs whose incompressibility would give a
complete classification of the kernelization complexity of $H$-free Edge
Deletion for every graph $H$ with at least 5 vertices. Analogous results follow
also for the $H$-free Edge Completion problem by simple complementation.
