Given a directed graph $G$ and two nodes $s,t$, decide whether there is some node $s'$ such that $s'$ is reachable from $s$ while $t$ is not reachable from $s'$.
I am wondering whether this problem is in NL.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ The problem is even NL-complete under logspace reduction. Check the Wikipedia page on st-connectivity. $\endgroup$– A.SchulzJul 21, 2012 at 21:06
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
It is in NL. Here is the outline of a possible proof:
- If you already fix s′, you can check whether s′ satisfies your condition or not in NL. Reachability is easy, non-reachability is by the Immerman–Szelepcsényi theorem, and taking the AND of two conditions is easy.
- Because there are only polynomially many possibilities for s′, you can test these possibilities one by one until you find the right s′ or find out that no such s′ exists. Alternatively, you can guess s′ by using nondeterminism.
