4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ The problem is even NL-complete under logspace reduction. Check the Wikipedia page on st-connectivity. $\endgroup$
    – A.Schulz
    Commented Jul 21, 2012 at 21:06

1 Answer 1

9
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.