Parameterized Lower Bound and Improved Kernel for Diamondfree Edge Deletion
R B, Sandeep and Sivadasan, N (2015) Parameterized Lower Bound and Improved Kernel for Diamondfree Edge Deletion. In: 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), 43 . DROPS, pp. 365376. ISBN 9783939897927

Text
34.pdf  Published Version Available under License Creative Commons Attribution. Download (497kB)  Preview 
Abstract
A diamond is a graph obtained by removing an edge from a complete graph on four vertices. A graph is diamondfree if it does not contain an induced diamond. The Diamondfree Edge Deletion problem asks to find whether there exist at most k edges in the input graph whose deletion results in a diamondfree graph. The problem was proved to be NPcomplete 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 Diamondfree Edge Deletion. We give an alternative proof of the NPcompleteness 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: 



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  
URI:  http://raiith.iith.ac.in/id/eprint/2229  
Publisher URL:  http://dx.doi.org/10.4230/LIPIcs.IPEC.2015.365  
Related URLs: 
Actions (login required)
View Item 
Statistics for this ePrint Item 