Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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.
