On polynomial kernelization of h-free edge deletion

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)


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].

[error in script]
IITH Creators:
IITH CreatorsORCiD
Item Type: Conference or Workshop Item (Paper)
Uncontrolled Keywords: Graphic methods; Polynomials Bounded degree; Cardinalities; Connected graph; General graph; Input graphs; Kernelization; Polynomial kernels; Triangle-free
Subjects: Computer science > Big Data Analytics
Divisions: Department of Computer Science & Engineering
Depositing User: Team Library
Date Deposited: 12 Jan 2015 06:17
Last Modified: 11 Jan 2016 07:17
URI: http://raiith.iith.ac.in/id/eprint/1317
Publisher URL: http://dx.doi.org/10.1007/978-3-319-13524-3_3
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 1317 Statistics for this ePrint Item