For a set of graphs H, the 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 ∈ H. In, it is shown that the problem is fixed-parameter tractable if H is of finite cardinality. However, it is proved in that if H is a singleton set containing H, for a laxge class of H, there exists no polynomial kernel unless coNP is contained in NP/poly. In this paper, we present a polynomial kernel for this problem for any fixed finite set H of connected graphs and when the input graphs are of bounded degree. We note that there are H-fkee Edge Deletion problems which remain NP-complete even for the bounded degree input graphs, for example Triangle-free Edge Deletion and Custer Edge Deletion(P_3-free Edge Deletion) . When 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. 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 and were raised as open problems in.
展开▼
