Split Vertex Deletion
A graph is a split graph if its vertices can be partitioned into a clique $C$ and an independent set $I$. In Split Vertex Deletion, we ask whether deleting at most $k$ vertices can turn a given graph into a split graph. Recall the forbidden induced subgraph characterization: $C_5$, $2K_2$, and $C_4$.
Part A
What is the running time of the exhaustive search algorithm for Split Vertex Deletion?
Part B
How many split partitions can a split graph on $n$ vertices have? Answer with the tightest bound that you can come up with.
Part C
What is the running time of the iterative compression algorithm for Split Vertex Deletion?
Solution:
Part A: $O(5^k \cdot \text{poly}(n))$
Part B: At most $O(n)$ partitions
Part C: $O(2^k \cdot \text{poly}(n))$