Sketching Cuts in Graphs and Hypergraphs
Dmitry Kogan, Robert Krauthgamer · 2015
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--ε)-approximation for Max-Cut must use n{1-O(ε)} space; moreover, beating 4/5-approximation requires polynomial space. For the sketching model, we show that every r-uniform hypergraph admits a (1+ ε)-cut-sparsifier (i.e., a weighted subhypergraph that approximately preserves all the cuts) with O(ε-2n(r+log n)) edges. We also make first steps towards sketching general CSPs (Constraint Satisfaction Problems).