<p>It seems your problem is in <span class="math-container">$NL$</span>. Here is an algorithm.</p>
<p>First, nondeterministically guess a path from <span class="math-container">$s$</span> to <span class="math-container">$t$</span>. If you guess incorrectly, <em>reject</em>. Call this algorithm <span class="math-container">$A$</span>.</p>
<p>Consider the following nondeterministic algorithm <span class="math-container">$B$</span>, which determines if there are at least two paths. Given a graph and <span class="math-container">$s,t$</span>, for all pairs of distinct edges <span class="math-container">$e,f$</span>, guess a path from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> that includes <span class="math-container">$e$</span> but not <span class="math-container">$f$</span>, then guess a path from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> that includes <span class="math-container">$f$</span> but not <span class="math-container">$e$</span>. If the guesses are correct, <em>accept</em>. If no acceptance occurs for all choices of <span class="math-container">$e$</span> and <span class="math-container">$f$</span>, <em>reject</em>. Note <span class="math-container">$B$</span> is implementable in nondeterministic logspace.</p>
<p>Now, the set <span class="math-container">$L(B)$</span> is the set of <span class="math-container">$s$</span>-<span class="math-container">$t$</span> graphs with at least two paths from <span class="math-container">$s$</span> to <span class="math-container">$t$</span>. Because <span class="math-container">$NL = coNL$</span>, the complement of <span class="math-container">$B$</span> is also in <span class="math-container">$NL$</span>, i.e., we can determine if <span class="math-container">$s$</span> and <span class="math-container">$t$</span> have <em>less</em> than two paths, in nondeterministic logspace.</p>
<p>The final algorithm is: &quot;Run <span class="math-container">$A$</span>. If <span class="math-container">$A$</span> accepts, then run the complement of <span class="math-container">$B$</span> and output its answer.&quot;</p>
<p>I don't know of a reference.</p>
<p><strong>UPDATE:</strong> If you really want a reference, check out the first paragraph of Section 3 of <a href="http://ftp.cs.rutgers.edu/pub/allender/isaac.pdf" rel="nofollow noreferrer">this paper</a>. But this is probably only one of many references that cite this consequence. It would be more reasonable to call the result &quot;folklore&quot; rather than citing a paper that happens to mention it.</p>
<p><strong>UPDATE 2:</strong> Let's suppose you want to determine if there is a unique simple path. In that case, algorithm <span class="math-container">$A$</span> 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 <span class="math-container">$B$</span>.</p>
<p>We want to rewrite algorithm <span class="math-container">$B$</span> so that it accepts iff there are at least two simple paths.</p>
<p>First consider the following polynomial-time algorithm for the problem. Find a shortest path <span class="math-container">$P$</span> from <span class="math-container">$s$</span> to <span class="math-container">$t$</span>. For every edge <span class="math-container">$e$</span> in <span class="math-container">$P$</span>, check if there is another <span class="math-container">$s$</span>-<span class="math-container">$t$</span> path that does not go through <span class="math-container">$e$</span>. If you find such a path then <em>accept</em>. If you never find another path then <em>reject</em>. Because <span class="math-container">$P$</span> is shortest, it does not have a cycle, and if there is another path that doesn't use some edge of <span class="math-container">$P$</span>, then there is another path which is simple and doesn't use some edge of <span class="math-container">$P$</span>. (This algorithm is used for the &quot;second shortest paths&quot; problem.)</p>
<p>We will implement this algorithm in <span class="math-container">$NL$</span>. If we had an <span class="math-container">$NL$</span> algorithm for querying the edges <span class="math-container">$e$</span> in a fixed path <span class="math-container">$P$</span>, we could implement the above in nondeterministic logspace: iterating through all edges <span class="math-container">$e$</span> in <span class="math-container">$P$</span>, guess an <span class="math-container">$s$</span>-<span class="math-container">$t$</span> path and check that for every edge visited along the way, none of them are equal to <span class="math-container">$e$</span>.</p>
<p>So what we need is a &quot;path oracle&quot;, an <span class="math-container">$NL$</span> algorithm with the property: given <span class="math-container">$i=1,\ldots,n$</span>, in every computation path the algorithm either reports the <span class="math-container">$i$</span>th edge on a particular fixed <span class="math-container">$s$</span>-<span class="math-container">$t$</span> path, or <em>reject</em>. We can get a path oracle by using <span class="math-container">$NL=coNL$</span> to isolate the lexicographically first path.</p>
<p>Here is a sketch of the path oracle.</p>
<blockquote>
<p>Find <span class="math-container">$k$</span>, the length of the shortest path from <span class="math-container">$s$</span> to <span class="math-container">$t$</span>, by trying all <span class="math-container">$k=1,\ldots,n$</span> and using <span class="math-container">$NL=coNL$</span>.</p>
<p>Set variables <span class="math-container">$u:=s$</span>, <span class="math-container">$x:=1$</span>, <span class="math-container">$j:=k$</span>.</p>
<p>For all neighbors <span class="math-container">$v$</span> of <span class="math-container">$u$</span> in lexicographical order,</p>
<p>Determine whether or not there is a path from <span class="math-container">$v$</span> to <span class="math-container">$t$</span> of length <span class="math-container">$j-1$</span> (using the result <span class="math-container">$NL=coNL$</span>).
More precisely, run the nondeterministic algorithm for <span class="math-container">$s$</span>-<span class="math-container">$t$</span> connectivity (of length <span class="math-container">$j-1$</span>) 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 <em>reject</em>.</p>
<p>If there is no path, proceed to the next neighbor. If you've exhausted all neighbors then <em>reject</em>.</p>
<p>If there is a path, then if <span class="math-container">$x=i$</span>, output <span class="math-container">$(u,v)$</span> as the <span class="math-container">$i$</span>th edge on the path from <span class="math-container">$s$</span> to <span class="math-container">$t$</span>. Otherwise increment <span class="math-container">$x$</span>, decrement <span class="math-container">$j$</span>, set <span class="math-container">$u := v$</span>, and start the for-loop again if <span class="math-container">$v \neq t$</span>.</p>
<p>If <span class="math-container">$x &lt; i$</span> after reaching <span class="math-container">$t$</span> output <em>bad <span class="math-container">$i$</span></em> (the given <span class="math-container">$i$</span> was too big).</p>
</blockquote>
<p>Given <span class="math-container">$i$</span>, this algorithm either outputs the <span class="math-container">$i$</span>th edge on the lexicographically shortest path <span class="math-container">$P$</span> from <span class="math-container">$s$</span> to <span class="math-container">$t$</span>, or rejects.</p>

CC BY-SA 3.0
2011-08-11T11:07:31.827Z
I thought to something similar but it uses linear space. Thanks for your answer!
Bruno
CC BY-SA 3.0
2011-08-11T11:24:38.337Z
I de-accept the answer for the moment. It is just in case somebody comes up with a reference.
Bruno
CC BY-SA 3.0
2011-08-11T15:02:09.120Z
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
CC BY-SA 3.0
2011-08-11T18:38:58.337Z
Kaveh, I don't know what you mean by "of the form mentioned"... We can just say the algorithm would get "stuck" if it reaches a degree-one node that is not a source or sink, and rejects. I am allowing non-simple paths to be counted as distinct from simple ones that may be subgraphs of it.
Ryan Williams
CC BY-SA 3.0
2011-08-11T19:42:33.280Z
Yes, as I stated above, the algorithm does not distinguish between simple paths and paths with cycles.
Ryan Williams
CC BY-SA 3.0
2011-08-11T20:50:28.780Z
I see, thanks, sorry for the confusion :), will remove my comments to keep here clean.
Kaveh
CC BY-SA 3.0
2011-08-12T08:10:17.907Z
Thanks very much for the detailed answer Ryan. I have to check it a bit more carefully but it seems that in my problems, all possible $s$-$t$-paths actually are simple, so that I can use your first algorithm.
Bruno
CC BY-SA 3.0
2011-08-12T08:29:37.797Z
@V Vinay: In [this paper](http://www.maths.uq.edu.au/%7Ekroese/ps/robkro_rev.pdf), 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](http://link.aip.org/link/?SMJCAT/8/410/1), 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
CC BY-SA 3.0
2011-08-12T08:41:31.840Z
Btw, the comment by Allender & Lange is enough to directly conclude.
Bruno
CC BY-SA 3.0
2011-08-11T10:55:45.680Z
2011-08-11T21:30:25.897Z
2020-06-17T09:38:08.363Z
Ryan Williams
<p>I would like to know whether the following problem can be decided in $\mathsf{NL}$ (nondeterministic logspace):</p>

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

<p>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).</p>

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

CC BY-SA 3.0
2011-08-11T15:36:37.130Z
Do you mean simple paths? Not clear it's the same in this context.
Lance Fortnow
CC BY-SA 3.0
2011-08-12T07:56:34.293Z
Good point, I mean simple paths indeed.
Bruno
<reference-request><graph-theory>
Complexity of Unique s-t-Connectivity
Bruno
# Complexity of Unique s-t-Connectivity

(Asked by: username_0 on 2011-08-11)

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

**Tags:** reference-request, graph-theory

> **Comments:**
> **username_1**: Do you mean simple paths? Not clear it's the same in this context.  
> **username_0**: Good point, I mean simple paths indeed.  

---

## 1 answers

### Answer by username_2 on 2011-08-11. Score: 16 | Accepted answer

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](http://ftp.cs.rutgers.edu/pub/allender/isaac.pdf). 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.

> **Comments:**
> **username_0**: I thought to something similar but it uses linear space. Thanks for your answer!  
> **username_0**: I de-accept the answer for the moment. It is just in case somebody comes up with a reference.  
> **username_3**: 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$  
> **username_2**: username_4, I don't know what you mean by "of the form mentioned"... We can just say the algorithm would get "stuck" if it reaches a degree-one node that is not a source or sink, and rejects. I am allowing non-simple paths to be counted as distinct from simple ones that may be subgraphs of it.  
> **username_2**: Yes, as I stated above, the algorithm does not distinguish between simple paths and paths with cycles.  
> **username_4**: I see, thanks, sorry for the confusion :), will remove my comments to keep here clean.  
> **username_0**: Thanks very much for the detailed answer Ryan. I have to check it a bit more carefully but it seems that in my problems, all possible $s$-$t$-paths actually are simple, so that I can use your first algorithm.  
> **username_0**: @username_3: In [this paper](http://www.maths.uq.edu.au/%7Ekroese/ps/robkro_rev.pdf), 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](http://link.aip.org/link/?SMJCAT/8/410/1), 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!  
> **username_0**: Btw, the comment by Allender & Lange is enough to directly conclude.  

---

