1
$\begingroup$

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}$?

$\endgroup$
3
  • 3
    $\begingroup$ Directed graph reachability is NL-complete. The only question is whether the restriction to out-degree 2 takes you into L. $\endgroup$ May 31, 2014 at 10:30
  • $\begingroup$ So you're saying it can be shown that $A$ is "at least" in $NL$ (if not $L$)...? $\endgroup$ May 31, 2014 at 11:13
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    May 31, 2014 at 17:48

1 Answer 1

5
$\begingroup$

The problem is NL-complete.

The fact that it's in NL, as stated in the comments, follows from the fact that this problem is a restriction of the reachability problem for directed graphs.

To see that it's NL-hard, we can reduce from the reachability problem:

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.