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

I want to show that $CO-2Col \le_L USTCON$ (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.

My solution is for an input graph $G$ the reduction outputs $(G',s,t)$ where $s$ an arbitrary vertex of $G$, $t$ is one of its neighbours and $G'=G^2$ namely an edge $(u,v)\in E(G')$,iff there is $w \in V (w \ne u,v)$ such that $(u,w)\in E(G)$ and $(w,v)\in E(G)$.

$G$ is bipartite iff $G'$ is not connected (and $s$ and $t$ belongs to different parts).

But this only works when the input graph $G$ is connected.

A counter example: (if we choose s,t to be A,B)

How can I improve my reduction that it will work at the unconnected case? or maybe a new reduction is needed?

Thanks!

Further hint: Take $n$ copies of your original graph (where $n$ is the number of vertices), and add a new vertex $s$. Connect $s$ to the $i$th vertex in the $i$th copy.
• Can you see how to make the graph connected without worrying about space? The same construction can also be implemented "in logspace", in the sense that you will be able to carry out the reduction in logspace; there is no need to store the modified graph anywhere, just as in your current reduction you don't need to store $G^2$ anywhere. – Yuval Filmus Mar 20 '14 at 17:51
• My only idea is to do something like dfs - start from arbitrary vertex, hold $|V|$ bits - one for every vertex I visited, and to keep on that way, and then connect unreachable vertex. But I have to save more than log bits... – David Mar 20 '14 at 18:19