The Sketching Complexity of Graph Cuts

by Alexandr Andoni, Robert Krauthgamer, David P. Woodruff

Comment: This work, which was posted as an arxiv TR is being merged with the work A Sketching Algorithm for Spectral Graph Sparsification (by Jiecao Chen, Bo Qin, David P. Woodruff, Qin Zhang).

Oded's comments

There are many interesting things about this work, but what I find most puzzling is that a two-sided approximation factor of the form $1\pm\eps$ is obtained at a complexity that is only linear (rather than quadratic) in $1/\eps$. I would welcome an intuitive explanation as how this happens.

Another interesting point is that the sketch is not merely a weighted subgraph, but this has an intuitive explanation: The sketch is composed of two parts, where the first allows to obtain only a rough approximation to the size of cuts, and the second is a sequence of sketches such that each sub-sketch allow to obtain the desired approximation provided that the value is roughly within some size.

The original abstract

We study the problem of sketching an input graph, so that given the sketch, one can estimate the weight of any cut in the graph within factor 1+eps. We present lower and upper bounds on the size of a randomized sketch, focusing on the dependence on the accuracy parameter eps>0.

First, we prove that for every eps>1/sqrt(n), every sketch that succeeds (with constant probability) in estimating the weight of all cuts (S,S bar) in an n-vertex graph (simultaneously), must be of size Omega(n/eps^2) bits. In the special case where the sketch is itself a weighted graph (which may or may not be a subgraph) and the estimator is the sum of edge weights across the cut in the sketch, i.e., a cut sparsifier, we show the sketch must have Omega(n/eps^2) edges, which is optimal. Despite the long sequence of work on graph sparsification, no such lower bound was known on the size of a cut sparsifier.

We then design a randomized sketch that, given eps>0 and an edge-weighted n-vertex graph, produces a sketch of size tildeO(n/eps) bits, from which the weight of any cut (S,S bar) can be reported, with high probability, within factor 1+eps. The previous upper bound is tildeO(n/eps^2) bits, which follows by storing a cut sparsifier (Bencz{\'u}r and Karger, 1996). To obtain this improvement, we critically use both that the sketch need only be correct on each fixed cut with high probability (rather than on all cuts), and that the estimation procedure of the data structure can be arbitrary (rather than a weighted subgraph). We also show a lower bound of Omega(n/eps) bits for the space requirement of any data structure achieving this guarantee.

Back to list of Oded's choices.