6
$\begingroup$

I'm trying to figure out the complexity of the reachability problem having as input a directed rooted forest, i.e., given a set of directed rooted trees and two vertices $s$ and $t$, tell if $s$ and $t$ are connected by a directed path belonging to one of such trees.

I know the problem is in $NL$, since STCON is $NL$-complete (and a directed rooted forest is just a kind of directed graph), but I can't manage to find a good lowerbound.

Any hint?

$\endgroup$

1 Answer 1

7
$\begingroup$

The problem is L-complete.

It’s easier to think about it when the edges are written backwards. That is, I will consider the problem formulated as follows: given a directed acyclic graph such that every node has out-degree at most $1$, and vertices $s$ and $t$, determine if $t$ is reachable from $s$.

To see that it is in L, just follow the unique path starting from $s$ until you reach either $t$, or a sink.

To see that it is L-hard, use a variant of the usual reduction showing L-hardness of undirected $s$-$t$-connectivity. Fix a deterministic logspace TM $M$; you may assume that it is endowed with a polynomially bounded clock, and whenever it is about to accept, it erases all work tapes and goes into a loop until exhausting the clock. Given an input $x$, consider the directed graph consisting of configurations of $M$, with edges given by the successor configuration relation, $s$ being the initial configuration, and $t$ being the accepting configuration (which is unique by our requirements on $M$). Since the TM is deterministic, each node has out-degree at most $1$, and since the TM is clocked, the graph is acyclic.

$\endgroup$
2
  • 1
    $\begingroup$ Thank you! Anyway, I've just figured out that the problem as formulated by you is what Cook & McKenzie call "Directed Forest Accessibility" (which indeed is L-complete), isn't it? $\endgroup$
    – Abel Freid
    Nov 16, 2021 at 13:19
  • $\begingroup$ Yes, that’s the same problem. $\endgroup$ Nov 16, 2021 at 13:21

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.