Is finding dead-end nodes in NL?

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.

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.

StackExchange Computer Science Q#2710, answer score: 9