Difference between revisions of "Open Problems:67"
| Line 5: | Line 5: | ||
}} | }} | ||
| − | + | The following construction is a hard instance for bipartiteness testing in sparse graphs {{cite|GoldreichR-02}}. | |
| − | |||
| − | |||
| − | 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 | + | 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? | |
| − | |||
| − | |||
| − | How much space is required to distinguish between these two graphs in | ||
Revision as of 18:42, 4 June 2014
| 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?
