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$ – David Richerby May 31 '14 at 10:30
  • $\begingroup$ So you're saying it can be shown that $A$ is "at least" in $NL$ (if not $L$)...? $\endgroup$ – so.very.tired May 31 '14 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 '14 at 17:48
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, privacy policy and cookie policy

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