HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

NL-Hardness of Target

Submitted by: @import:stackexchange-cs··
0
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!

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.

Context

StackExchange Computer Science Q#110435, answer score: 2

Revisions (0)

No revisions yet.