N R, Aravind and R B, Sandeep and Sivadasan, N
(2014)
On polynomial kernelization of hfree edge deletion.
In: 9th International Symposium on Parameterized and Exact Computation, IPEC 2014, 1012 September 2014, Wroclaw; Poland.
Full text not available from this repository.
(
Request a copy)
Abstract
For a set of graphs H, the Hfree 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 [3], it is shown that the problem is fixedparameter tractable if H is of finite cardinality. However, it is proved in [4] that if H is a singleton set containing H, for a large class of H, there exists no polynomial kernel unless coNP ⊆ 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 Hfree Edge Deletion problems which remain NPcomplete even for the bounded degree input graphs, for example Trianglefree Edge Deletion [2] and Custer Edge Deletion(P3free Edge Deletion) [15]. When H contains K1, s, we obtain a stronger resulta polynomial kernel for Ktfree input graphs (for any fixed t > 2). We note that for s > 9, there is an incompressibility result for K1, sfree Edge Deletion for general graphs [5]. Our result provides first polynomial kernels for Clawfree Edge Deletion and Line Edge Deletion for Ktfree input graphs which are NPcomplete even for K4free graphs [23] and were raised as open problems in [4, 19].
[error in script]
Actions (login required)

View Item 