Consider the following problem:
$$A=\left\{ (G(V,E),s,t)\mid\text{conditions 1, 2, 3 and 4 hold} \right\}$$
- $G$ is a directed graph.
- $s,t\in V$.
- There is a simple path from $s$ to $t$ (a simple path is a path that visits every vertex not more than once).
- $\forall v\in V: \deg^+(v)\leq 2$ (in words: every vertex in $V$ has outdegree at most 2).
Out of the following classes: $\mathsf{L,NL,P,NP,co-NP,EXP}$, I need to determine what is the smallest class (with respect to inclusion) that has $A$ in it.
My idea is: since every vertex has outdegree at most 2, I can write a function $F$, s.t for every $v\in V$ I'll recursively call $F$ with the two adjacent vertices of $v$.
The termination condition will be either if $\deg^+(v)=0$ (we've reached a leaf node) or $v$ has alredy been visited (this will make sure the path is simple) or $v=t$ (we've found a path to $t$), thus concluding that $A\in P$ (the complexity of the described algorithm is $n\log n$).
I'm just not sure if that is the best that can be done. Can it be shown that $A$ is in $\mathsf{L}$ or $\mathsf{NL}$?