Incompressibility of H-free edge modification problems: Towards a dichotomy

• Published in: arXiv.org 2021-09
• Main Authors: Marx, Dániel, Sandeep, R B
• Format: Article
• Language: English
• Subjects: Apexes; Classification; Complexity; Deletion; Editing; Graph theory; Graphs; Incompressibility; Kernels; Polynomials
• ISSN: 2331-8422

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.