Sketching cuts in graphs and hypergraphs

DOI10.1145/2688073.2688093MaRDI QIDQ2989051zbMATH OpenOpenAlexFDO

Authors Robert Krauthgamer, Dmitry Kogan

Publication date 19 May 2017

Published in Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.2391

zbMATH Keywords

hypergraphsMax-cutsketchingsparsifiersstreaming

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

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(epsilo{n}^{-2}n(r+logn))$ edges. We also make first steps towards sketching general CSPs (Constraint Satisfaction Problems).

Recommendations

• Streaming Lower Bounds for Approximating MAX-CUT
• Optimal lower bounds for sketching graph cuts
• (1 + (1))-approximation to MAX-CUT requires linear space
• An optimal space lower bound for approximating MAX-CUT
• Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches

Cited in

(37)

• Dynamic graph stream algorithms in \(o(n)\) space
• Intractability of min- and max-cut in streaming graphs
• Faster connectivity in low-rank hypergraphs via expander decomposition
• Hypergraph \(k\)-cut in randomized polynomial time
• Better streaming algorithms for the maximum coverage problem
• Multicriteria cuts and size-constrained \(k\)-cuts in hypergraphs
• On sketching quadratic forms
• Minimum cuts and sparsification in hypergraphs
• (1 + (1))-approximation to MAX-CUT requires linear space
• A Heuristic Solution of a Cutting Problem Using Hypergraphs
• Computing exact minimum cuts without knowing the graph
• Streaming complexity of approximating Max 2CSP and Max Acyclic Subgraph
• Sublinear algorithms for MAXCUT and correlation clustering
• Online disjoint set cover without prior knowledge
• Sparsification of Binary CSPs
• Hypergraph Cuts with General Splitting Functions
• An optimal space lower bound for approximating MAX-CUT
• Sparsification of binary CSPs
• Optimal lower bounds for sketching graph cuts
• Sparsification of two-variable valued constraint satisfaction problems
• Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches
• Minimum Cut and Minimum k -Cut in Hypergraphs via Branching Contractions
• Multicriteria Cuts and Size-Constrained k-Cuts in Hypergraphs.
• (Noisy) gap cycle counting strikes back: random order streaming lower bounds for connected components and beyond
• Streaming approximation resistance of every ordering CSP
• Splitting-off in hypergraphs
• Almost-tight bounds on preserving cuts in classes of submodular hypergraphs
• Cut sparsification and succinct representation of submodular hypergraphs
• Splitting-off in hypergraphs
• Vertex sparsifiers for hyperedge connectivity
• Additive sparsification of CSPs
• Sparsification of directed graphs via cut balance
• Sublinear time hypergraph sparsification via cut and edge sampling queries
• Hypergraph connectivity augmentation in strongly polynomial time
• A theory of spectral CSP sparsification
• Near-optimal hypergraph sparsification in insertion-only and bounded-deletion streams
• Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs

This page was built for publication: Sketching cuts in graphs and hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2989051)