Speaker:

Kangyi Tian (University of Electronic Science and Technology of China)

Time:

• 16:20-17:20 (Time in Beijing)
• October 13, 2023 (Friday)

Venue:

518, Research Building 4

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.