# Complexity of Unique s-t-Connectivity

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

-
Do you mean simple paths? Not clear it's the same in this context. –  Lance Fortnow Aug 11 '11 at 15:36
Good point, I mean simple paths indeed. –  Bruno Aug 12 '11 at 7:56

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.

-
I thought to something similar but it uses linear space. Thanks for your answer! –  Bruno Aug 11 '11 at 11:07
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$ –  V Vinay Aug 11 '11 at 15:02
Yes, as I stated above, the algorithm does not distinguish between simple paths and paths with cycles. –  Ryan Williams Aug 11 '11 at 19:42
@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! –  Bruno Aug 12 '11 at 8:29
Btw, the comment by Allender & Lange is enough to directly conclude. –  Bruno Aug 12 '11 at 8:41