# Bipartite Problem is Log-Space Reducible To $s$-$t$ Undirected Connectivity

Prove that the problem of determining if graph is bipartite is computationally equivalent under log-space reductions to $s$-$t$ undirected connectivity.

Problem of $s$-$t$ undirected connectivity is the following given an undirected graph $G = (V, E)$ and two designated vertices, $s$ and $t$, determine whether there is a path from $s$ to $t$ in $G$.

I assume the idea is to consider mapping from graph $G$ to bipartite graph $G'$, there should be a correspondence between edges of $G$ and edges of bipartite graph $G'$, and between edges of $G$ and the edges that violates the bipartite property of graph $G'$. The problem is I cannot come up with such correspondence.

I would appreciate any idea.

## 1 Answer

Here are some ideas on how to reduce checking bipartiteness to undirected non-connectivity:

1. A graph is bipartite iff it has no odd cycles.
2. Suppose we guess that vertex $v$ participates in a cycle of length $2k+1$. Using a layered graph, we can check whether it is the case using undirected connectivity.
3. We can also implement a disjunction ("or") using undirected connectivity.

Here are some ideas for the other direction:

1. Every graph can be made bipartite by splitting every edge into a path of length $2$.
2. What happens when we join $s$ and $t$, after splitting the edges?
• 1.what do you mean by layered graph? 2. You said: "guess". What do you mean by 'guess'? You cannot guess because it requires non-determinism. 3. Why do you want to implement a disjunction? – Carol Aug 9 '17 at 8:29
• A layered graph is one in which vertices are partitioned into numbered layers, and edges connect vertices belonging to consecutive layers. – Yuval Filmus Aug 9 '17 at 9:46
• By "guessing" I mean going over all possibilities. – Yuval Filmus Aug 9 '17 at 9:46
• As for the disjunction, I'll let you figure that one out. – Yuval Filmus Aug 9 '17 at 9:47
• You don’t need to build it. You only need to be able to simulate it, i.e. to answer vertex and edge queries. – Yuval Filmus Jan 19 at 7:57