# Near-linear Size Hypergraph Cut Sparsifiers

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Sep 2020.

## Built on by (most cited first, 4 of 4)

- [Sparsification of Decomposable Submodular Functions](https://mlsanity.com/paper/2201.07289/) (2022)
- [Cheeger Inequalities for Directed Graphs and Hypergraphs Using Reweighted Eigenvalues](https://mlsanity.com/paper/2211.09776/) (2022)
- [Sublinear Algorithms for Hierarchical Clustering](https://mlsanity.com/paper/2206.07633/) (2022)
- [Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts](https://mlsanity.com/paper/2507.14835/) (2025)

## Abstract (arXiv)

Cuts in graphs are a fundamental object of study, and play a central role in the study of graph algorithms. The problem of sparsifying a graph while approximately preserving its cut structure has been extensively studied and has many applications. In a seminal work, Bencz'ur and Karger (1996) showed that given any n-vertex undirected weighted graph G and a parameter varepsilon ∈ (0,1), there is a near-linear time algorithm that outputs a weighted subgraph G' of G of size tildeO(n/varepsilon2) such that the weight of every cut in G is preserved to within a (1 ± varepsilon)-factor in G'. The graph G' is referred to as a em (1 ± varepsilon)-approximate cut sparsifier of G. A natural question is if such cut-preserving sparsifiers also exist for hypergraphs. Kogan and Krauthgamer (2015) initiated a study of this question and showed that given any weighted hypergraph H where the cardinality of each hyperedge is bounded by r, there is a polynomial-time algorithm to find a (1 ± varepsilon)-approximate cut sparsifier of H of size tildeO(fracnrvarepsilon2). Since r can be as large as n, in general, this gives a hypergraph cut sparsifier of size tildeO(n2/varepsilon2), which is a factor n larger than the Bencz'ur-Karger bound for graphs. It has been an open question whether or not Bencz'ur-Karger bound is achievable on hypergraphs. In this work, we resolve this question in the affirmative by giving a new polynomial-time algorithm for creating hypergraph sparsifiers of size tildeO(n/varepsilon2).