Abstract
We study the problem of sketching an input graph, so that, given the sketch, one can estimate the value (capacity) of any cut in the graph up to a small approximation, 1+epsilon. Classical constructions imply sketches of size essentially proportional to n and the square of 1/epsilon [Benczur, Karger 1996].
We construct sketches whose size is only linear in 1/epsilon (and n*polylog n). The improved size comes at a cost of a slightly weaker guarantee: our construction is a randomized scheme which, given accuracy epsilon and an n-vertex graph G=(V,E), produces a sketch from which the capacity of any cut (S,V\S) can be reported, with high probability, within approximation factor (1+epsilon).
We also show the improved dependence on epsilon is possible only under the weaker guarantee: namely, if a sketch succeeds in estimating the capacity of all cuts (S,V\S) in the graph simultaneously, it must be of size Omega(n/epsilon^2) bits.