2012/08/06 by Marek Cygan, Marcin Pilipczuk, Cygan, Marek +1
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1208.1248
arxiv created 2012/08/06 · arxiv updated 2012/08/07
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 fixed-parameter algorithms for Split Vertex Deletion parameterized by k: 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. Plugging the currently best fixed-parameter algorithm for Vertex Cover due to Chen et al. [TCS 2010], we obtain an algorithm that solves Split Vertex Deletion in time O(1.2738k * kO(log k) + nO(1)). To achieve our goal, we prove the following structural result that may be of independent interest: for any graph G we may compute a family P of size nO(log n) containing partitions of V(G) into two parts, such for any two disjoint subsets XC, XI of V(G) where G[XC] is a clique and G[XI] is an independent set, there is a partition in P which contains all vertices of XC on one side and all vertices of XI on the other.