Log-Space Reduction $USTCON\le_L CO-2Col$

Question

I want to show that $USTCON\le_L CO-2Col$ (Log-Space reduction)

$USTCON$ The $s-t$ connectivity problem for undirected graphs is called $USTCON$.

Input: An undirected graph $G=(V,E)$, $s,t \in V$. Output: 1 iff $s$ is connected to $t$ in $G$.

$CO-2Col$ A graph is $2$-colorable if there is a way to color the vertices of $G$ with $2$ colors, such that for every edge the two vertices on the edge are colored differently. $CO-2Col$ is the following problem:

Input: An undirected graph $G$. Output: 1 iff $G$ is NOT $2$-colorable.

I know this can be solved by simply using the $USTCON$ decision algorithm and then output a bipartite or non-bipartite graph accordingly. But is there any other reduction that actually changes the input graph?

Answer 1

Let USTCON2 be the following problem: given a graph $G$ and two vertices $s,t$, decide whether there is a walk from $s$ to $t$ of even length. Let us show first that USTCON2 reduces to co2COL.

Given a graph $G = (V,E)$ and two vertices $s,t$, construct a new graph whose vertex set consists of two copies of $V$. For every $(a,b) \in E$, connect $a$ in the first copy to $b$ in the second copy, and $a$ in the second copy to $b$ in the first copy. So far the graph is bipartite. Now connect $s$ and $t$ in the first copy. The new graph is bipartite iff there is no path of even length from $s$ to $t$ in the original graph.

Now let us reduce USTCON to USTCON2. Given a graph $G = (V,E)$ and two vertices $s,t$, add two new vertices $x,y$, and edges $(s,x),(x,y),(y,s)$. There is a walk from $s$ to $t$ in the original graph iff there is a walk of even length from $s$ to $t$ in the new graph.