Sketching Cuts in Graphs and Hypergraphs

Abstract

Sketching and streaming algorithms are in the forefront of current research directions for cut problems in graphs. In the streaming model, we show that $(1-\epsilon )$-approximation for Max-Cut must use $n^{1-O(\epsilon )}$ space; moreover, beating $4/5$-approximation requires polynomial space. For the sketching model, we show that $r$-uniform hypergraphs admit a $(1+\epsilon )$-cut-sparsifier (i.e., a weighted subhypergraph that approximately preserves all the cuts) with $O({\epsilon }^{-2}n(r+\log n))$ edges. We also make first steps towards sketching general CSPs (Constraint Satisfaction Problems).

References in corpus (4)

• Single pass sparsification in the streaming model with edge deletions
• Approximation Algorithms for Hypergraph Small Set Expansion and Small Set Vertex Expansion
• The Sketching Complexity of Graph Cuts
• Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms

Cited by in corpus (21)

• On Fully Dynamic Graph Sparsifiers
• Kernelization via Sampling with Applications to Dynamic Graph Streams
• Space-Efficient Interior Point Method, with applications to Linear Programming and Maximum Weight Bipartite Matching
• The Sketching Complexity of Graph Cuts
• Computing exact minimum cuts without knowing the graph
• Sparsification of Binary CSPs
• Graph Streaming Lower Bounds for Parameter Estimation and Property Testing via a Streaming XOR Lemma
• Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems
• A note on approximate strengths of edges in a hypergraph
• Hardness of Distributed Optimization
• Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order
• Towards Tight Bounds for Spectral Sparsification of Hypergraphs
• Additive Sparsification of CSPs
• Dynamic Graph Stream Algorithms in $o(n)$ Space
• Metric Sublinear Algorithms via Linear Sampling
• Augmented Sparsifiers for Generalized Hypergraph Cuts with Applications to Decomposable Submodular Function Minimization
• Near-linear Size Hypergraph Cut Sparsifiers
• Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries
• Noisy Boolean Hidden Matching with Applications
• Sparsification of Two-Variable Valued CSPs
• Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-kSAT