Parameterized Lower Bound and Improved Kernel for Diamond-free Edge Deletion

R B, Sandeep and Sivadasan, N (2015) Parameterized Lower Bound and Improved Kernel for Diamond-free Edge Deletion. In: 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), 43 . DROPS, pp. 365-376. ISBN 978-3-939897-92-7

34.pdf - Published Version
Available under License Creative Commons Attribution.

Download (497kB) | Preview


A diamond is a graph obtained by removing an edge from a complete graph on four vertices. A graph is diamond-free if it does not contain an induced diamond. The Diamond-free Edge Deletion problem asks to find whether there exist at most k edges in the input graph whose deletion results in a diamond-free graph. The problem was proved to be NP-complete and a polynomial kernel of O(k^4) vertices was found by Fellows et. al. (Discrete Optimization, 2011). In this paper, we give an improved kernel of O(k^3) vertices for Diamond-free Edge Deletion. We give an alternative proof of the NP-completeness of the problem and observe that it cannot be solved in time 2^{o(k)} * n^{O(1)}, unless the Exponential Time Hypothesis fails.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Item Type: Book Section
Uncontrolled Keywords: edge deletion problems, polynomial kernelization
Subjects: Computer science > Special computer methods
Computer science > Big Data Analytics
Divisions: Department of Computer Science & Engineering
Depositing User: Team Library
Date Deposited: 03 Mar 2016 04:32
Last Modified: 03 Mar 2016 04:33
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 2229 Statistics for this ePrint Item