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

arXiv: https://arxiv.org/abs/2404.16131 · HTML: https://mlsanity.com/paper/2404.16131/

## Key facts

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

## Builds on (most cited first, 17 of 17)

- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [A Deterministic Linear Program Solver in Current Matrix Multiplication Time](https://mlsanity.com/paper/1910.11957/) (2019)
- [Maximum Flow and Minimum-Cost Flow in Almost-Linear Time](https://mlsanity.com/paper/2203.00671/) (2022)
- [Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs](https://mlsanity.com/paper/1412.0681/) (2014)
- [Correlation Clustering in Constant Many Parallel Rounds](https://mlsanity.com/paper/2106.08448/) (2021)
- [Differentially Private Correlation Clustering](https://mlsanity.com/paper/2102.08885/) (2021)
- [Unifying Sparsest Cut, Cluster Deletion, and Modularity Clustering Objectives with Correlation Clustering](https://mlsanity.com/paper/1712.05825/) (2017)
- [Correlation Clustering via Strong Triadic Closure Labeling: Fast Approximation Algorithms and Practical Lower Bounds](https://mlsanity.com/paper/2111.10699/) (2021)
- [Local Correlation Clustering with Asymmetric Classification Errors](https://mlsanity.com/paper/2108.05697/) (2021)
- [Fast Combinatorial Algorithms for Min Max Correlation Clustering](https://mlsanity.com/paper/2301.13079/) (2023)
- [Correlation Clustering with Constrained Cluster Sizes and Extended Weights Bounds](https://mlsanity.com/paper/1411.0547/) (2014)
- [Correlation Clustering with Asymmetric Classification Errors](https://mlsanity.com/paper/2108.05696/) (2021)
- [On the Relation of Strong Triadic Closure and Cluster Deletion](https://mlsanity.com/paper/1803.00807/) (2018)
- [Partial Optimality in Cubic Correlation Clustering](https://mlsanity.com/paper/2302.04694/) (2023)
- [Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Rounds](https://mlsanity.com/paper/2307.06723/) (2023)
- [Faster Approximation Algorithms for Parameterized Graph Clustering and Edge Labeling](https://mlsanity.com/paper/2306.04884/) (2023)
- [(Sub)linear kernels for edge modification problems towards structured graph classes](https://mlsanity.com/paper/2105.09566/) (2021)

## 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.