Speaker: 操宜新副教授，香港理工大学计算学系

Inviter: 陈旭瑾研究员

Title: Cluster Vertex Deletion on Chordal Graphs

Language: English

Time & Venue: 2026.04.01 11:00-12:00 数学院南楼620

Abstract: In the cluster vertex deletion problem, we are given a vertex-weighted graph and asked to delete a minimum-weight set of vertices so that the resulting graph is a cluster graph (a graph whose components are all cliques). We present a polynomial-time algorithm for this problem on chordal graphs, resolving an open question posed in different contexts by Cao et al. [Theoretical Computer Science, 2018], Aprile et al. [Mathematical Programming, 2023], and Hsieh et al. [Algorithmica, 2024]. We use dynamic programming over clique trees and reduce the computation of the optimal subproblem value to the minimization of a submodular set function.