N R, Aravind and R B, Sandeep and Sivadasan, N
(2014)
On polynomial kernelization of h-free edge deletion.
In: 9th International Symposium on Parameterized and Exact Computation, IPEC 2014, 10-12 September 2014, Wroclaw; Poland.
Full text not available from this repository.
(
Request a copy)
Abstract
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 [3], it is shown that the problem is fixed-parameter 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 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(P3-free Edge Deletion) [15]. When H contains K1, s, we obtain a stronger result-a polynomial kernel for Kt-free input graphs (for any fixed t > 2). We note that for s > 9, there is an incompressibility result for K1, s-free Edge Deletion for general graphs [5]. Our result provides first polynomial kernels for Claw-free Edge Deletion and Line Edge Deletion for Kt-free input graphs which are NP-complete even for K4-free graphs [23] and were raised as open problems in [4, 19].
Actions (login required)
 |
View Item |
Altmetric
Altmetric