Problem 67: Difficult Instance for Max-Cut in the Streaming Model
| Suggested by | Robert Krauthgamer |
|---|---|
| Source | Bertinoro 2014 |
| Short link | https://sublinear.info/67 |
The following construction is a hard instance for bipartiteness testing in sparse graphs [GoldreichR-02].
Let $G$ be a graph consisting of a cycle of length $n$ (where $n$ is even) and a random matching. It is known that with high probability, $G$ is an expander and at least $0.01 n$ edges have to be removed to turn it into a bipartite graph. Let $G'$ be a graph consisting of a cycle of length $n$ and a random matching, with the constraint that the matching must consist only of "even chords": these are chords that are an even number of vertices apart on the cycle. It is easy to see that $G'$ is bipartite.
The total number of edges in each graph is $3n/2$. It is easy to see that
- $G'$ has a cut of size $3n/2$,
- with high probability $G$ has no cut of size greater than $(3/2 - 0.01)n$.
How much space is required to distinguish between these two graphs in the streaming model?
