Let's consider the problem:

Prove that decision whether a graph is bipartite is in $LOGSPACE$.

I am convinced that I should use Reingold's theorem. I know that I test whether graph contains an odd-length cycle.

For a given graph $G = (V,E)$ I can define the graph $$G' = (V', E') \\ V' = \{ v^1, v^2 | v \in V \} \\ E' = \{(u^1, w^2), (u^2, w^1) | (u,w) \in E\}$$

And now, the vertex $v$ resides in odd-length cycle iff there is a path between $v^1$ and $v^2$.

But, how can I construct $G'$ using $LOG$ memory?


Your construction shows that checking whether an undirected graph is bipartite is logspace reducible to PATH (deciding whether there exists a path between two vertices in an undirected graph).

Recall that if $A$ is logspace reducible to $B$ and $B\in L$, then $A\in L$. To decide $A$ in logspace, you don't actually compute the reduction (as its output can be of polynomial length), but compute a single bit of the reduction whenever it is requested. More concretely, suppose $f$ is a logspace reduction from $A$ to $B$. To decide $A$, given input $x$, execute the logspace machine for $B$ and keep a counter $i$ for the location on its input tape. Whenever $B$ wants to read a symbol from its input, compute the $i$'th bit of $f(x)$, which requires only logarithmic space (as $f$ is a logspace reduction from $A$ to $B$).

This show that you don't actually need to construct $G'$ entirely. You only need to compute a given bit of its adjacency matrix in logarithmic space.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.