A cubic vertex kernel for Diamond-free Edge Deletion and more

2015/07/31 by Sandeep, R. B., Sivadasan, Naveen
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1507.08792

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⁴) vertices was found by Fellows et. al. (Discrete Optimization, 2011). In this paper, we give an improved kernel of O(k³) vertices for Diamond-free Edge Deletion. Further, we give an O(k²) vertex kernel for a related problem Diamond,K_t-free Edge Deletion, where t≥ 4 is any fixed integer. To complement our results, we prove that these problems are NP-complete even for K₄-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)⋅ |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.

Related

• Improved Kernels and Algorithms for Claw and Diamond Free Edge Deletion Based on Refined Observations
• Polynomial kernelization for removing induced claws and diamonds
• A Polynomial Kernel for Diamond-Free Editing
• On Polynomial Kernelization of H-free Edge Deletion
• Kernel for Kt-free edge deletion