A cubic vertex kernel for Diamond-free Edge Deletion and more
Preprint
Abstract
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 whether there exist at most $k$ edges in the input graph $G$ whose deletion results in a diamond-free graph. For this problem, 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. Further, we give an $O(k^2)$ vertex kernel for a related problem {Diamond,K_t}-free Edge Deletion, where $t\geq 4$ is any fixed integer. To complement our results, we prove that these problems are NP-complete even for $K_4$-free graphs and can be solved neither in subexponential time (i.e., $2^{o(|G|)}$) nor in parameterized subexponential time (i.e., $2^{o(k)}\cdot |G|^{O(1)}$), unless Exponential Time Hypothesis fails. Our reduction implies the hardness and lower bound for a general class of problems, where these problems come as a special case.
Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Polynomial Kernelization for Removing Induced Claws and DiamondsTheory of Computing Systems, 2016
- Compressing Bounded Degree GraphsLecture Notes in Computer Science, 2016
- Parameterized Lower Bounds and Dichotomy Results for the NP-completeness of H-free Edge Modification ProblemsLecture Notes in Computer Science, 2016
- Incompressibility of $H$ H -Free Edge Modification ProblemsAlgorithmica, 2014
- Two edge modification problems without polynomial kernelsDiscrete Optimization, 2013
- Which Problems Have Strongly Exponential Complexity?Journal of Computer and System Sciences, 2001
- Face Covers and the Genus Problem for Apex GraphsJournal of Combinatorial Theory, Series B, 2001
- Fixed-parameter tractability of graph modification problems for hereditary propertiesInformation Processing Letters, 1996
- Edge-Deletion ProblemsSIAM Journal on Computing, 1981