Cluster deletion is an NP-hard graph clustering objective with applications
in computational biology and social network analysis, where the goal is to
delete a minimum number of edges to partition a graph into cliques. We first
provide a tighter analysis of two previous approximation algorithms, improving
their approximation guarantees from 4 to 3. Moreover, we show that both
algorithms can be derandomized in a surprisingly simple way, by greedily taking
a vertex of maximum degree in an auxiliary graph and forming a cluster around
it. One of these algorithms relies on solving a linear program. Our final
contribution is to design a new and purely combinatorial approach for doing so
that is far more scalable in theory and practice.

删除最小数量的边将图划分为团体是一种 NP 困难的图聚类目标，在计算生物学和社交网络分析中具有应用。我们提供了两种先前近似算法的更严格的分析，将其近似保证从 4 改进到 3。此外，我们展示了这两种算法可以以出人意料的简单方式解除随机化，通过在辅助图中贪婪地选择具有最大度的顶点并围绕其形成一个聚类。其中一种算法依赖于解决一个线性规划问题。我们最后的贡献是设计一种新的纯组合方法来解决这个问题，在理论和实践中更加可扩展。