# To show that a graph-problem is in $L$ or $NL$

Consider the following problem:

$$A=\left\{ (G(V,E),s,t)\mid\text{conditions 1, 2, 3 and 4 hold} \right\}$$

1. $G$ is a directed graph.
2. $s,t\in V$.
3. There is a simple path from $s$ to $t$ (a simple path is a path that visits every vertex not more than once).
4. $\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}$?

• Directed graph reachability is NL-complete. The only question is whether the restriction to out-degree 2 takes you into L. – David Richerby May 31 '14 at 10:30
• So you're saying it can be shown that $A$ is "at least" in $NL$ (if not $L$)...? – so.very.tired May 31 '14 at 11:13
• so.very.tired, you've been given a humongous hint. Now your next step is to do some research to understand and think through the implications of that hint. Rather than immediately asking a question that just parrots back what you've already been told, go research the hint. Go familiarize yourself with NL. Go find the result that directed graph reachability is NL-complete and make sure you are familiar with it. See if you can tell what that implies for your problem. Think hard about this for a while, then if you're still stuck, try to formulate a more precise, well-informed question. – D.W. May 31 '14 at 17:48

Consider a graph $G=(V,E)$ and vertices $s,t$. We transform $G$ to a graph $G'$ with out degree at most $2$, as follows.
For every vertex $v$ with out-neighbors $u_1,...,u_k$ ($k\ge 3$), construct vertices $v_1,...,v_{k-1}$ where there are edges from $v_i$ to $u_i$ and to $v_{i+1}$. The incoming edges to $v$ are now directed to $v_1$, and $v$ is removed.
It is not hard to see that there is a path from $s$ to $t$ in $G$ iff there is a path from $s_1$ to $t_1$ in $G'$. Also, this reduction can be implemented in log-space. Thus, your problem is NL-complete.