2
$\begingroup$

When revising for an upcoming exam in complexity theory, I came across this problem on the final part of a question, which I was unable to solve:

$ TARGET = \{<G, t> : t\ is\ reachable\ from\ every\ other\ node\ in\ G\}$

Now we are allowed to use any standardly known problems that are NL-Hard in this part of the question. I considered between reducing from $REACH$ or $\overline{REACH}$, its complement - where $REACH$ is the standard NL-Complete problem. I thought perhaps $\overline{REACH}$ would reduce more naturally to $TARGET$ as the negation of $REACH$'s membership logical formula would be "$<G,s,t>$ where for all paths $P$ originating from $s$, $t$ is not on $P$".

However, I did not get very far from here. Then again, it is quite late in the evening and perhaps I am missing an obvious reduction here.

Many thanks for any hints and pointers!

$\endgroup$
1
$\begingroup$

Let us reduce REACH to TARGET. Given an instance $(G,s,t)$ of REACH, add edges from all nodes other than $s$ to $s$ to form a new graph $G'$. If $t$ is reachable from $s$ in $G$ then it is reachable from all other nodes in $G'$ using the new edges. Conversely, if $t$ is reachable from all other nodes in $G'$, then in particular it is reachable from $s$ in $G'$. Even if this path uses any of the new edges, all they can do is bring it back to the starting point, and so $t$ is reachable from $s$ already in $G$.

Altogether, we have shown that $(G,s,t)$ is a yes instance of REACH iff $(G',t)$ is a yes instance of TARGET.

$\endgroup$
  • $\begingroup$ Awesome, it seems so obvious now! $\endgroup$ – CowNorris Jun 10 at 12:31

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.