Get all the updates for this publication
Vertex deletion on split graphs: Beyond 4-hitting set
Vertex deletion problems on graphs involve finding a set of minimum number of vertices whose deletion results in a graph with some specific property. In a recent study on vertex deletion problems on split graphs, it was shown that transforming a split graph to a block graph or a threshold graph using minimum number of vertex deletions is NP-hard. We call the decision version of these problems as Split to Block Vertex Deletion (SBVD) and Split to Threshold Vertex Deletion (STVD), respectively. In this paper, we study the parameterized complexity of these problems with the number of vertex deletions, k, as a parameter. These problems are implicit 4-Hitting Set and thus admit an algorithm with running time , a kernel with vertices, and a 4-approximation algorithm. In this paper, we exploit the structural properties of the concerned graph classes and obtain a kernel for SBVD with vertices and FPT algorithms for SBVD and STVD with running times and , respectively. We further give improved approximation algorithms for SBVD and STVD.
Journal | Data powered by TypesetTheoretical Computer Science |
---|---|
Publisher | Data powered by TypesetElsevier |
ISSN | 03043975 |
Open Access | No |