Kangyi Tian: Parameterized Algorithms for Cluster Vertex Deletion on Degree-4 Graphs and General Graphs

Abstract

In the Cluster Vertex Deletion problem, we are given a graph $G$ and an integer $k$, and the goal is to determine whether we can delete at most $k$ vertices from $G$ to make the remaining graph a cluster, i.e., a graph with each connected component being a complete graph. In this talk, we show that Cluster Vertex Deletion can be solved in $O^*(1.7549^k)$ time, improving the previous result of $O^*(1.811^k)$. To obtain this result, one crucial step is to show that Cluster Vertex Deletion on graphs of maximum degree at most 4 can be solved in $O^*(1.7485^k)$ time. After this step, we know that the graph will always have a vertex of degree at least 5. Then by adopting the previous method of automated generation of searching trees, we can obtain the result on general graphs.