2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, there was a small parity issue, but hopefully it's coorected now. $\endgroup$ – Yuval Filmus Jun 18 at 8:23

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.