On Polynomial Kernelization of $$\mathcal {}$$- free Edge Deletion

For a set \(\mathcal {H}\) of graphs, the \(\mathcal {H}\)-free Edge Deletion problem is to decide whether there exist at most k edges in the input graph, for some \(k\in \mathbb {N}\), whose deletion results in a graph without an induced copy of any of the graphs in \(\mathcal {H}\) . The problem is known to be fixed-parameter tractable if \(\mathcal {H}\) is of finite cardinality. In this paper, we present a polynomial kernel for this problem for any fixed finite set \(\mathcal {H}\) of connected graphs for the case where the input graphs are of bounded degree. We use a single kernelization rule which deletes vertices ‘far away’ from the induced copies of every \(H\in \mathcal {H}\) in the input graph. With a slightly modified kernelization rule, we obtain polynomial kernels for \(\mathcal {H}\)-free Edge Deletion under the following three settings: \(\mathcal {H}\) contains \(K_{1,s}\) and \(K_t\); \(\mathcal {H}\) contains \(K_{1,s}\) and the input graphs are \(K_t\)-free; \(\mathcal {H}\) contains \(K_{t}\) and the input graphs are \(K_{1,s}\)-free; where \(s>1\) and \(t>2\) are any fixed integers. Our result provides the first polynomial kernels for Claw-free Edge Deletion and Line Edge Deletion for \(K_t\)-free input graphs which are known to be NP-complete even for \(K_4\)-free graphs.