On Polynomial Kernelization of H-free Edge Deletion

Aravind, N R and Sandeep, R B and Sivadasan, N (2017) On Polynomial Kernelization of H-free Edge Deletion. Algorithmica, 79 (3). pp. 654-666. ISSN 0178-4617

Preview

Text (arXiv copy)
1407.7156.pdf - Accepted Version
Download (195kB) | Preview

Abstract

For a set H of graphs, the H-free 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 fixed-parameter 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 H-free Edge Deletion under the following three settings:

[error in script]

IITH Creators: