Kernel for Kt-free edge deletion

2019/08/09 by Tsur, Dekel
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1908.03600

Abstract

In the K_t-free edge deletion problem, the input is a graph G and an integer k, and the goal is to decide whether there is a set of at most k edges of G whose removal results a graph with no clique of size t. In this paper we give a kernel to this problem with O(k^t-1) vertices and edges.

Related

• Improved Kernels and Algorithms for Claw and Diamond Free Edge Deletion Based on Refined Observations
• A cubic vertex kernel for Diamond-free Edge Deletion and more
• On Polynomial Kernelization of H-free Edge Deletion
• Polynomial kernelization for removing induced claws and diamonds
• A polynomial kernel for Block Graph Deletion