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

Given a graph G and an integer k, the H-FREE 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. 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 where H-FREE EDGE EDITING admits a polynomial kernel. Towards this goal, we obtain a set 7-t of nine 5-vertex graphs such that if for every H is an element of H, H-FREE EDGE EDITING is incompressible and the complexity assumption NP not subset of 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. We obtain similar results also for H-FREE EDGE DELETION/COMPLETION. (c) 2021 Elsevier Inc. All rights reserved.