2020/09/10 by Yu Chen, Sanjeev Khanna, Chen, Yu +3 · 3 citations
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Interconnection Networks and Systems #Low-power high-performance VLSI design #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.2009.04992
openalex publication_date 2020/09/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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úr and Karger (1996) showed that given any n-vertex undirected weighted graph G and a parameter ε ∈ (0,1), there is a near-linear time algorithm that outputs a weighted subgraph G' of G of size O(n/ε2) such that the weight of every cut in G is preserved to within a (1 ± ε)-factor in G'. The graph G' is referred to as a \em (1 ± ε)-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 ± ε)-approximate cut sparsifier of H of size O((nr)/(ε2)). Since r can be as large as n, in general, this gives a hypergraph cut sparsifier of size O(n2/ε2), which is a factor n larger than the Benczúr-Karger bound for graphs. It has been an open question whether or not Benczúr-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 O(n/ε2).