Faster Parameterized Algorithms for Split Graph Deletion

partitioned into two sets such that the subgraph induced on one of them is
a complete graph and the subgraph induced on the other is an independent
set. We study the problem of deleting the minimum number of vertices
or edges from a given input graph so that the resulting graph is split.We
give efficient fixed-parameter algorithms and polynomial sized kernels for
the problem. More precisely,

1. for Split Vertex Deletion, the problem of determining whether there are
k vertices whose deletion results in a split graph, we give an
O(2^k)^4 algorithm improving on the previous best bound of
O(2.32^k ). We also give an O(k^3 )-sized kernel for the problem.

2. For Split Edge Deletion, the problem of determining whether there are k
edges whose deletion results in a split graph, we give an O(2^O(
k log k) ) algorithm. We also prove the existence of an O(k^2 )
kernel.