mlsanityData to 13 Oct 2026

Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better

arXiv 2404.16131 ↗First posted 24 Apr 2024cs.DS cs.LG cs.SIcited by 0

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 13 Oct 2026). Builds on 17 of its 46 references that are in the map. First posted on arXiv 24 Apr 2024.

Builds on

17 of 46 references.

References · 17

  1. 2018Solving Linear Programs in the Current Matrix Multiplication Timecited by 100
  2. 2019A Deterministic Linear Program Solver in Current Matrix Multiplication Timecited by 42
  3. 2022Maximum Flow and Minimum-Cost Flow in Almost-Linear Timecited by 28
  4. 2014Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphscited by 27
  5. 2021Correlation Clustering in Constant Many Parallel Roundscited by 15
  6. 2021Differentially Private Correlation Clusteringcited by 13
  7. 2017Unifying Sparsest Cut, Cluster Deletion, and Modularity Clustering Objectives with Correlation Clusteringcited by 12
  8. 2021Correlation Clustering via Strong Triadic Closure Labeling: Fast Approximation Algorithms and Practical Lower Boundscited by 12
  9. 2021Local Correlation Clustering with Asymmetric Classification Errorscited by 7
  10. 2023Fast Combinatorial Algorithms for Min Max Correlation Clusteringcited by 7
  11. 2014Correlation Clustering with Constrained Cluster Sizes and Extended Weights Boundscited by 6
  12. 2021Correlation Clustering with Asymmetric Classification Errorscited by 6
5 more
  1. 2018On the Relation of Strong Triadic Closure and Cluster Deletioncited by 4
  2. 2023Partial Optimality in Cubic Correlation Clusteringcited by 3
  3. 2023Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Roundscited by 3
  4. 2023Faster Approximation Algorithms for Parameterized Graph Clustering and Edge Labelingcited by 2
  5. 2021(Sub)linear kernels for edge modification problems towards structured graph classescited by 1

Built on by

Not cited yet.