Dekel Tsur

In the SPLIT TO BLOCK VERTEX DELETION and SPLIT TO THRESHOLD VERTEX DELETION problems the input is a split graph G and an integer k, and the goal is to decide whether there is a set S of vertices of size at most k such that G−S is a block graph and G−S is a threshold graph, respectively. In this paper we give algorithms for these problems whose running times are O^⁎(2.076^k) and O^⁎(1.619^k), respectively.