patternMinor
NL-Hardness of Target
Viewed 0 times
targethardnessstackoverflow
Problem
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 = \{ : 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 "$$ 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!
$ TARGET = \{ : 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 "$$ 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!
Solution
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.
Altogether, we have shown that $(G,s,t)$ is a yes instance of REACH iff $(G',t)$ is a yes instance of TARGET.
Context
StackExchange Computer Science Q#110435, answer score: 2
Revisions (0)
No revisions yet.