11
$\begingroup$

I would like to know whether the following problem can be decided in $\mathsf{NL}$ (nondeterministic logspace):

Given a directed graph $G$ with two distinguished vertices $s$ and $t$, is there a unique path from $s$ to $t$ in $G$?

I feel that it is likely to be in $\mathsf{NL}$ since we can decide both if there is a $s$-$t$-path and if there is no such path. Yet, counting the number of such paths is $\mathsf{\sharp P}$-hard (Valiant, 1979).

So my questions: Do you have references about this? Is it obvious that it is in $\mathsf{NL}$? Or that it is not in $\mathsf{NL}$?

$\endgroup$
2
  • 5
    $\begingroup$ Do you mean simple paths? Not clear it's the same in this context. $\endgroup$ Aug 11, 2011 at 15:36
  • 1
    $\begingroup$ Good point, I mean simple paths indeed. $\endgroup$
    – Bruno
    Aug 12, 2011 at 7:56

1 Answer 1

16
$\begingroup$

It seems your problem is in $NL$. Here is an algorithm.

First, nondeterministically guess a path from $s$ to $t$. If you guess incorrectly, reject. Call this algorithm $A$.

Consider the following nondeterministic algorithm $B$, which determines if there are at least two paths. Given a graph and $s,t$, for all pairs of distinct edges $e,f$, guess a path from $s$ to $t$ that includes $e$ but not $f$, then guess a path from $s$ to $t$ that includes $f$ but not $e$. If the guesses are correct, accept. If no acceptance occurs for all choices of $e$ and $f$, reject. Note $B$ is implementable in nondeterministic logspace.

Now, the set $L(B)$ is the set of $s$-$t$ graphs with at least two paths from $s$ to $t$. Because $NL = coNL$, the complement of $B$ is also in $NL$, i.e., we can determine if $s$ and $t$ have less than two paths, in nondeterministic logspace.

The final algorithm is: "Run $A$. If $A$ accepts, then run the complement of $B$ and output its answer."

I don't know of a reference.

UPDATE: If you really want a reference, check out the first paragraph of Section 3 of this paper. But this is probably only one of many references that cite this consequence. It would be more reasonable to call the result "folklore" rather than citing a paper that happens to mention it.

UPDATE 2: Let's suppose you want to determine if there is a unique simple path. In that case, algorithm $A$ doesn't have to change: if there is a path at all then there is a simple path. I believe the following modification will work for algorithm $B$.

We want to rewrite algorithm $B$ so that it accepts iff there are at least two simple paths.

First consider the following polynomial-time algorithm for the problem. Find a shortest path $P$ from $s$ to $t$. For every edge $e$ in $P$, check if there is another $s$-$t$ path that does not go through $e$. If you find such a path then accept. If you never find another path then reject. Because $P$ is shortest, it does not have a cycle, and if there is another path that doesn't use some edge of $P$, then there is another path which is simple and doesn't use some edge of $P$. (This algorithm is used for the "second shortest paths" problem.)

We will implement this algorithm in $NL$. If we had an $NL$ algorithm for querying the edges $e$ in a fixed path $P$, we could implement the above in nondeterministic logspace: iterating through all edges $e$ in $P$, guess an $s$-$t$ path and check that for every edge visited along the way, none of them are equal to $e$.

So what we need is a "path oracle", an $NL$ algorithm with the property: given $i=1,\ldots,n$, in every computation path the algorithm either reports the $i$th edge on a particular fixed $s$-$t$ path, or reject. We can get a path oracle by using $NL=coNL$ to isolate the lexicographically first path.

Here is a sketch of the path oracle.

Find $k$, the length of the shortest path from $s$ to $t$, by trying all $k=1,\ldots,n$ and using $NL=coNL$.

Set variables $u:=s$, $x:=1$, $j:=k$.

For all neighbors $v$ of $u$ in lexicographical order,

Determine whether or not there is a path from $v$ to $t$ of length $j-1$ (using the result $NL=coNL$). More precisely, run the nondeterministic algorithm for $s$-$t$ connectivity (of length $j-1$) and the algorithm for its complement, simultaneously. When one of them accepts, go with its answer (it must be correct; both cannot accept). If both reject then reject.

If there is no path, proceed to the next neighbor. If you've exhausted all neighbors then reject.

If there is a path, then if $x=i$, output $(u,v)$ as the $i$th edge on the path from $s$ to $t$. Otherwise increment $x$, decrement $j$, set $u := v$, and start the for-loop again if $v \neq t$.

If $x < i$ after reaching $t$ output bad $i$ (the given $i$ was too big).

Given $i$, this algorithm either outputs the $i$th edge on the lexicographically shortest path $P$ from $s$ to $t$, or rejects.

$\endgroup$
9
  • $\begingroup$ I thought to something similar but it uses linear space. Thanks for your answer! $\endgroup$
    – Bruno
    Aug 11, 2011 at 11:07
  • 5
    $\begingroup$ I agree it is really folklore. It is an immediate consequence of the collapse of the $NL$ hierarchy. Also, the counting problem in not #P-complete. It is in #L, which in turn is in $NC^2$ $\endgroup$
    – V Vinay
    Aug 11, 2011 at 15:02
  • 2
    $\begingroup$ Yes, as I stated above, the algorithm does not distinguish between simple paths and paths with cycles. $\endgroup$ Aug 11, 2011 at 19:42
  • 1
    $\begingroup$ @V Vinay: In this paper, the authors refer to Valiant's paper The complexity of enumeration and reliability problems as proving the $\sharp\mathsf P$-completeness of the problem. I just checked in Valiant's paper, and it is problem 14 (p414). Am I misunderstanding something? Maybe you spoke about non-simple paths, and the complexity changes dramatically in this case? Thanks! $\endgroup$
    – Bruno
    Aug 12, 2011 at 8:29
  • 1
    $\begingroup$ Btw, the comment by Allender & Lange is enough to directly conclude. $\endgroup$
    – Bruno
    Aug 12, 2011 at 8:41

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.