2026-08-16T00:56:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5597 2024-03-06T10:36:38Z ddc:004 open_access

Parameterized Lower Bound and Improved Kernel for Diamond-free Edge Deletion Sandeep, R. B. Sivadasan, Naveen edge deletion problems polynomial kernelization 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik R. B. Sandeep and Naveen Sivadasan 2015 Is Part Of LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2015.365 urn:nbn:de:0030-drops-55976 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.365 eng https://creativecommons.org/licenses/by/3.0/legalcode