# NL-Hardness of Target

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!

## 1 Answer

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.

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