Near-linear Size Hypergraph Cut Sparsifiers

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 $\varepsilon\in(0, 1)$, there is a near-linear time algorithm that outputs a weighted subgraph $G^{\prime}$ of $G$ of size $\tilde{O}(n/\varepsilon^{2})$ such that the weight of every cut in $G$ is preserved to within a ( $1\pm\varepsilon$ )-factor in $G^{\prime}$. The graph $G^{\prime}$ is referred to as a ( $1\pm\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\pm\varepsilon$ )-approximate cut sparsifier of $H$ of size $\tilde{O}(\frac{nr}{\varepsilon^{2}})$. Since $r$ can be as large as $n$, in general, this gives a hypergraph cut sparsifier of size $\tilde{O}(n^{2}/\varepsilon^{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 $\tilde{O}(n/\varepsilon^{2})$.

Authors

• Yu Chen 0039
• Sanjeev Khanna
• Ansh Nagda

Keywords

• Approximation algorithms
• Buildings
• Weight measurement
• Task analysis
• Sun
• Standards
• Size measurement
• Role In Study
• Polynomial-time Algorithm
• Running Time
• Proof Of Theorem
• Linear Dependence
• Maximum Strength
• Weight Function
• Edge Weights
• Maximum Ratio
• Minimum Strength
• Weight Assignment
• Cut Set
• Multiset
• Standard Graph
• Induced Subgraph
• Subset Of Vertices
• Edge Strength
• Small Cut
• Number Of Cuts
• Logarithmic Factor
• Minimum Cut
• Weaker Notion
• High Probability
• Weight Balance
• Maximum And Minimum
• Vertex Degree
• Minimum Weight