# 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. Aug 11 '11 at 15:36
• Good point, I mean simple paths indeed. 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! 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$ Aug 11 '11 at 15:02
• Yes, as I stated above, the algorithm does not distinguish between simple paths and paths with cycles. 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! Aug 12 '11 at 8:29
• Btw, the comment by Allender & Lange is enough to directly conclude. Aug 12 '11 at 8:41