3
$\begingroup$

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)

Counter example

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

Thanks!

$\endgroup$
2
$\begingroup$

Hint: Extend the input graph to a connected graph which is bipartite iff the original graph is bipartite.

If the original graph is not bipartite, then the new graph will a fortiori not be bipartite. The more difficult direction is ensuring that when the original is bipartite, the new edges do not render it non-bipartite. This property is satisfied as long as the edges that you introduce do not close an odd cycle.

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.

$\endgroup$
  • $\begingroup$ I don't understand how should I make the input graph connected in log space? I think I need at least one bit for every edge\vertex and this is not log space. Am I missing something here? $\endgroup$ – David Mar 19 '14 at 22:14
  • $\begingroup$ You don't have to actually store the modified input graph. You just need to be able to compute with it. You can do this in logspace (depending on your solution, naturally). $\endgroup$ – Yuval Filmus Mar 20 '14 at 1:55
  • $\begingroup$ I still can't figure it out... Any more hints? I just can't see how can I make this graph connected in logspace. $\endgroup$ – David Mar 20 '14 at 15:11
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Mar 20 '14 at 17:51
  • $\begingroup$ 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... $\endgroup$ – David Mar 20 '14 at 18:19

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.