<p>The problem is <strong>L</strong>-complete.</p>
<p>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 <span class="math-container">$1$</span>, and vertices <span class="math-container">$s$</span> and <span class="math-container">$t$</span>, determine if <span class="math-container">$t$</span> is reachable from <span class="math-container">$s$</span>.</p>
<p>To see that it is in <strong>L</strong>, just follow the unique path starting from <span class="math-container">$s$</span> until you reach either <span class="math-container">$t$</span>, or a sink.</p>
<p>To see that it is <strong>L</strong>-hard, use a variant of the usual reduction showing <strong>L</strong>-hardness of undirected <span class="math-container">$s$</span>-<span class="math-container">$t$</span>-connectivity. Fix a deterministic logspace TM <span class="math-container">$M$</span>; 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 <span class="math-container">$x$</span>, consider the directed graph consisting of configurations of <span class="math-container">$M$</span>, with edges given by the successor configuration relation, <span class="math-container">$s$</span> being the initial configuration, and <span class="math-container">$t$</span> being the accepting configuration (which is unique by our requirements on <span class="math-container">$M$</span>). Since the TM is deterministic, each node has out-degree at most <span class="math-container">$1$</span>, and since the TM is clocked, the graph is acyclic.</p>

CC BY-SA 4.0
2021-11-16T13:19:04.063Z
Thank you! Anyway, I've just figured out that the problem as formulated by you is what [Cook & McKenzie](http://www.cs.utoronto.ca/~sacook/homepage/cook_mckenzie.pdf#page=4) call "Directed Forest Accessibility" (which indeed is L-complete), isn't it?
Abel Freid
CC BY-SA 4.0
2021-11-16T13:21:01.463Z
Yes, that’s the same problem.
Emil Jeřábek
CC BY-SA 4.0
2021-11-16T12:47:56.867Z
2021-11-16T13:00:16.230Z
2021-11-16T13:00:16.230Z
Emil Jeřábek
<p>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 <span class="math-container">$s$</span> and <span class="math-container">$t$</span>, tell if <span class="math-container">$s$</span> and <span class="math-container">$t$</span> are connected by a directed path belonging to one of such trees.</p>
<p>I know the problem is in <span class="math-container">$NL$</span>, since STCON is <span class="math-container">$NL$</span>-complete (and a directed rooted forest is just a kind of directed graph), but I can't manage to find a good lowerbound.</p>
<p>Any hint?</p>

<complexity-classes><reductions><tree><directed-acyclic-graph><complexity-theory>
Complexity of reachability in directed rooted forests
Abel Freid
# Complexity of reachability in directed rooted forests

(Asked by: username_0 on 2021-11-16)

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?

**Tags:** complexity-classes, reductions, tree, directed-acyclic-graph, complexity-theory

---

## 1 answers

### Answer by username_1 on 2021-11-16. Score: 7 | Accepted answer

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.

> **Comments:**
> **username_0**: Thank you! Anyway, I've just figured out that the problem as formulated by you is what [Cook & McKenzie](http://www.cs.utoronto.ca/~sacook/homepage/cook_mckenzie.pdf#page=4) call "Directed Forest Accessibility" (which indeed is L-complete), isn't it?  
> **username_1**: Yes, that’s the same problem.  

---

