Aravind, N R and Sandeep, R B and Sivadasan, N
(2016)
On Polynomial Kernelization of Hfree Edge Deletion.
Algorithmica.
ISSN 01784617
(In Press)
Abstract
For a set H of graphs, the Hfree Edge Deletion problem is to decide whether there exist at most k edges in the input graph, for some k∈N, whose deletion results in a graph without an induced copy of any of the graphs in H . The problem is known to be fixedparameter tractable if H is of finite cardinality. In this paper, we present a polynomial kernel for this problem for any fixed finite set 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∈H in the input graph. With a slightly modified kernelization rule, we obtain polynomial kernels for Hfree Edge Deletion under the following three settings:
[error in script]
Actions (login required)

View Item 