On Polynomial Kernelization of \(\mathcal {H}\)-free Edge Deletion

For a set of graphs \(\mathcal {H}\), the \(\mathcal {H}\) -free Edge Deletion problem asks to find whether there exist at most \(k\) edges in the input graph whose deletion results in a graph without any induced copy of \(H\in \mathcal {H}\). In [3], it is shown that the problem is fixed-parameter tractable if \(\mathcal {H}\) is of finite cardinality. However, it is proved in [4] that if \(\mathcal {H}\) is a singleton set containing \(H\), for a large class of \(H\), there exists no polynomial kernel unless \(coNP\subseteq NP/poly\). In this paper, we present a polynomial kernel for this problem for any fixed finite set \(\mathcal {H}\) of connected graphs and when the input graphs are of bounded degree. We note that there are \(\mathcal {H}\) -free Edge Deletion problems which remain NP-complete even for the bounded degree input graphs, for example Triangle-free Edge Deletion [2] and Custer Edge Deletion( \(P_3\) -free Edge Deletion) [15]. When \(\mathcal {H}\) contains \(K_{1,s}\), we obtain a stronger result - a polynomial kernel for \(K_t\)-free input graphs (for any fixed \(t> 2\)). We note that for \(s>9\), there is an incompressibility result for \(K_{1,s}\) -free Edge Deletion for general graphs [5]. Our result provides first polynomial kernels for Claw-free Edge Deletion and Line Edge Deletion for \(K_t\)-free input graphs which are NP-complete even for \(K_4\)-free graphs [23] and were raised as open problems in [4, 19].