Cheap and Secure Web Hosting Provider : See Now

[Solved]: Log-Space Reduction $CO-2Col \le_L USTCON$

, , No Comments
Problem Detail: 

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


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$.


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?


Asked By : David

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source :

 Ask a Question

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback