Quadratic vertex kernel for split vertex deletion

A graph is called a split graph if its vertex set can be partitioned into a clique and an independent set. Split graphs have rich mathematical structure and interesting algorithmic properties making it one of the most well-studied special graph classes. In the SPLIT VERTEX DELETION problem, given a graph and a positive integer k, the objective is to test whether there exists a subset of at most kvertices whose deletion results in a split graph. In this paper, we design a kernel for this problem with O(k(2)) vertices, improving upon the previous cubic bound known. Also, by giving a simple reduction from the VERTEX COVER problem, we establish that SPLIT VERTEX DELETION does not admit a kernel with O(k(2-epsilon)) edges, for any epsilon > 0, unless NP subset of coNP/poly. (c) 2020 Elsevier B.V. All rights reserved.