SPLIT VERTEX DELETION meets VERTEX COVER: New fixed-parameter and exact exponential-time algorithms

In the SPLIT VERTEX DELETION problem, given a graph G and an integer k, we ask whether one can delete k vertices from the graph G to obtain a split graph (i.e., a graph, whose vertex set can be partitioned into two sets: one inducing a clique and the second one inducing an independent set). In this paper we study exact (exponential-time) and fixed-parameter algorithms for SPLIT VERTEX DELETION. We show that, up to a factor quasipolynomial in k and polynomial in n, the SPLIT VERTEX DELETION problem can be solved in the same time as the well-studied VERTEX COVER problem. By plugging in the currently best fixed-parameter algorithm for VERTEX COVER due to Chen et al. [Theor. Comput Sci. 411 (40-42) (2010) 3736-3756], we obtain an algorithm that solves SPLIT VERTEX DELETION in time O(-1.2738(k)k(O(logk)) + n(3)). We show that all maximal induced split subgraphs of a given n-vertex graph can be listed in O(3(n/3) n(O(logn))) time. To achieve our goals, we prove the following structural result that may be of independent interest: for any graph G we may compute a family P of size n(O(logn)) containing partitions of V(C) into two parts, such that for any two disjoint sets X-C, X-I subset of V (G) where G[X-C] is a clique and G[X-I] is an independent set, there is a partition in P which contains all vertices of X-C on one side and all vertices of X-I on the other. Moreover, the family P can be enumerated in O(n(O(logn))) time. (C) 2013 Elsevier B.V. All rights reserved.