3 papers
cs.DS2026
Cluster Deletion is as Hard to Approximate as Vertex Cover
Yixin Cao, Ying Xu
Recent breakthroughs in Cluster Editing have motivated attempts to adapt these approaches to obtain better-than- approximations for Cluster Deletion. We rule out this possibilit…
cs.DM2026
Minimum Sum Set Cover: Structures and Algorithm
Zhongyi Zhang, Yixin Cao
A set cover of a hypergraph is a set of vertices intersecting every hyperedge. In the minimum sum set cover problem, vertices are selected one by one; each edge pays the positi…
cs.DS2026
Cluster Vertex Deletion on Chordal Graphs
Yixin Cao, Peng Li
We present a polynomial-time algorithm for the cluster vertex deletion problem on chordal graphs, resolving an open question posed in different contexts by Cao et al. [Theoretical…