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

Text (arXiv copy)
1407.7156.pdf - Accepted Version

Download (195kB) | Preview


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:
IITH CreatorsORCiD
Item Type: Article
Uncontrolled Keywords: Polynomial kernelization,Edge deletion problems,bounded-degree graphs
Subjects: Computer science > Big Data Analytics
Divisions: Department of Computer Science & Engineering
Depositing User: Team Library
Date Deposited: 13 Oct 2016 10:17
Last Modified: 28 Sep 2017 06:45
URI: http://raiith.iith.ac.in/id/eprint/2803
Publisher URL: https://doi.org/10.1007/s00453-016-0215-y
OA policy: http://www.sherpa.ac.uk/romeo/issn/0178-4617/
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 2803 Statistics for this ePrint Item