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.2738kkO(logk)+n3)O(1.2738kkO(logk)+n3).
• We show that all maximal induced split subgraphs of a given n  -vertex graph can be listed in O(3n/3nO(logn))O(3n/3nO(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 PP of size nO(logn)nO(logn) containing partitions of V(G)V(G) into two parts, such that for any two disjoint sets XC,XI⊆V(G)XC,XI⊆V(G) where G[XC]G[XC] is a clique and G[XI]G[XI] is an independent set, there is a partition in PP which contains all vertices of XCXC on one side and all vertices of XIXI on the other. Moreover, the family PP can be enumerated in O(nO(logn))O(nO(logn)) time.

► Split Vertex Deletion is analyzed from the parameterized point of view.
► We show that SplitVD can be solved essentially in the same time as Vertex Cover.
► Moreover, all maximal split induced subgraphs can be enumerated in 3n/3nO(logn)3n/3nO(logn) time.