We consider the problem of estimating the value of max cut in a graph in the streaming model of computation. At one extreme, there is a trivial 2-approximation for this problem that uses only O(log n) space, namely, count the number of edges and output half of this value as the estimate for max cut value. On the other extreme, if one allowsÕ(n) space, then a near-optimal solution to the max cut value can be obtained by storing anÕ(n)-size sparsifier that essentially preserves the max cut. An intriguing question is if polylogarithmic space suffices to obtain a non-trivial approximation to the max-cut value (that is, beating the factor 2). It was recently shown that the problem of estimating the size of a maximum matching in a graph admits a non-trivial approximation in poly-logarithmic space. Our main result is that any streaming algorithm that breaks the 2-approximation barrier requiresΩ( √ n) space even if the edges of the input graph are presented in random order. Our result is obtained by exhibiting a distribution over graphs which are either bipartite or 1 2 -far from being bipartite, and establishing that Ω( √ n) space is necessary to differentiate between these two cases. Thus as a direct corollary we obtain that Ω( √ n) space is also necessary to test if a graph is bipartite or 1 2 -far from being bipartite. We also show that for any ǫ > 0, any streaming algorithm that obtains a (1 + ǫ)-approximation to the max cut value when edges arrive in adversarial order requires n 1−O(ǫ) space, implying that Ω(n) space is necessary to obtain an arbitrarily good approximation to the max cut value.
Independently of our work, Kapralov, Khanna and Sudan REF study the same problem of approximating MaxCut in the streaming model.
Streaming Lower Bounds for Approximating MAX-CUT
ArXiv
ArXiv
Mathematics Computer Science