<p>Every simple path is uniquely determined by the subset of vertices that it passes through: if you topologically order the DAG (arbitrarily) then a path through any subset of vertices must go through those vertices in the same order given by the topological order. So (since <span class="math-container">$s$</span> and <span class="math-container">$t$</span> must always be included) there are at most <span class="math-container">$2^{n-2}$</span> paths.</p>

<p>This bound is tight, for a complete DAG (one in which every pair of vertices is connected by an edge, oriented consistently with a single topological order).</p>

CC BY-SA 4.0
2019-04-10T20:25:26.250Z
2019-04-10T20:25:26.250Z
David Eppstein
<p>Let <span class="math-container">$G = (N, A)$</span> be a connected acyclic digraph (DAG). Furthermore, let <span class="math-container">$s \in N$</span> and <span class="math-container">$t \in N$</span> be two vertices on this graph, such that <span class="math-container">$t$</span> is reachable from <span class="math-container">$s$</span>.</p>

<p><strong>My problem is</strong>: <em>how many simple <span class="math-container">$s-t$</span> paths exist on this DAG?</em><br>
Most precisely, how can we write a function on the number of nodes <span class="math-container">$|N|$</span> which is an upper bound for the number of simple <span class="math-container">$s-t$</span> paths in <span class="math-container">$G$</span>?</p>

<hr>

<p>I'm aware that exists a polynomial-time dynamic programming algorithm that counts the number of such paths (see <a href="https://cs.stackexchange.com/questions/3078/algorithm-that-finds-the-number-of-simple-paths-from-s-to-t-in-g">here</a>) and that is an enumeration problem. This algorithm is <a href="https://cstheory.stackexchange.com/questions/25707/the-complexity-of-counting-simple-paths-in-a-directed-graph">#P-Complete</a> on general digraphs, but is in <span class="math-container">$P$</span> for DAGs, as pointed out by @Joshua Grochow in the comments.</p>

<p>I'm also aware that this number is <a href="https://cs.stackexchange.com/questions/84619/finding-all-unique-paths-from-a-source-to-a-sink-in-a-specially-formed-dag">exponential on the size of the longest <span class="math-container">$s-t$</span> path</a>.<br>
However, I don't see a relation between this function and the number of nodes in the graph.</p>

<p>Thanks in advance :)</p>

CC BY-SA 4.0
2019-04-10T18:51:11.580Z
It is #P-complete on general directed graphs, not on DAGs. On DAGs, "path" and "simple path" are the same concept. The dynamic programming algorithm puts this problem in P. The longest s-t path in a DAG is at most the depth of the DAG which is at most the number of vertices.
Joshua Grochow
CC BY-SA 4.0
2019-04-10T18:54:05.457Z
Yeah, all paths in a DAG are simple, by definition. But, since one can counts the number of paths in polynomial-time, can we also assume that there is a polynomial number of paths (in respect to the number of nodes of the DAG)? In the case you pointed out, there is just one path from $s$ to $t$ in $G$.
Iago Carvalho
CC BY-SA 4.0
2019-04-10T19:34:48.007Z
No, the number of paths can be exponential. Consider for example the graph on n vertices {1,...,n} with an edge from i to j whenever i<j.
Emil Jeřábek
CC BY-SA 4.0
2019-04-10T20:06:26.147Z
OK, I accept that. This question came in my mind because such a structure was used within an NP-Hard proof. See the article http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.101.142&rep=rep1&type=pdf (Section 3, first and second paragraphs of Page 4). In this paper, the reduction lies on enumerating all $s-t$ paths of a DAG and constructing one node for each of them. I really don't know if those results are valid or not.
Iago Carvalho
CC BY-SA 4.0
2019-04-11T00:58:08.043Z
You didn't get their reduction right...
Yota Otachi
<reference-request><graph-theory><directed-acyclic-graph><shortest-path>
Number of simple paths between two vertices in a DAG
Iago Carvalho
# Number of simple paths between two vertices in a DAG

(Asked by: username_0 on 2019-04-10)

Let $G = (N, A)$ be a connected acyclic digraph (DAG). Furthermore, let $s \in N$ and $t \in N$ be two vertices on this graph, such that $t$ is reachable from $s$.

**My problem is**: *how many simple $s-t$ paths exist on this DAG?*  
Most precisely, how can we write a function on the number of nodes $|N|$ which is an upper bound for the number of simple $s-t$ paths in $G$?

---

I'm aware that exists a polynomial-time dynamic programming algorithm that counts the number of such paths (see [here](https://cs.stackexchange.com/questions/3078/algorithm-that-finds-the-number-of-simple-paths-from-s-to-t-in-g)) and that is an enumeration problem. This algorithm is [#P-Complete](https://cstheory.stackexchange.com/questions/25707/the-complexity-of-counting-simple-paths-in-a-directed-graph) on general digraphs, but is in $P$ for DAGs, as pointed out by @username_1 in the comments.

I'm also aware that this number is [exponential on the size of the longest $s-t$ path](https://cs.stackexchange.com/questions/84619/finding-all-unique-paths-from-a-source-to-a-sink-in-a-specially-formed-dag).  
However, I don't see a relation between this function and the number of nodes in the graph.

Thanks in advance :)

**Tags:** reference-request, graph-theory, directed-acyclic-graph, shortest-path

> **Comments:**
> **username_1**: It is #P-complete on general directed graphs, not on DAGs. On DAGs, "path" and "simple path" are the same concept. The dynamic programming algorithm puts this problem in P. The longest s-t path in a DAG is at most the depth of the DAG which is at most the number of vertices.  
> **username_0**: Yeah, all paths in a DAG are simple, by definition. But, since one can counts the number of paths in polynomial-time, can we also assume that there is a polynomial number of paths (in respect to the number of nodes of the DAG)? In the case you pointed out, there is just one path from $s$ to $t$ in $G$.  
> **username_2**: No, the number of paths can be exponential. Consider for example the graph on n vertices {1,...,n} with an edge from i to j whenever i<j.  
> **username_0**: OK, I accept that. This question came in my mind because such a structure was used within an NP-Hard proof. See the article http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.101.142&rep=rep1&type=pdf (Section 3, first and second paragraphs of Page 4). In this paper, the reduction lies on enumerating all $s-t$ paths of a DAG and constructing one node for each of them. I really don't know if those results are valid or not.  
> **username_3**: You didn't get their reduction right...  

---

## 1 answers

### Answer by username_4 on 2019-04-10. Score: 12 | Accepted answer

Every simple path is uniquely determined by the subset of vertices that it passes through: if you topologically order the DAG (arbitrarily) then a path through any subset of vertices must go through those vertices in the same order given by the topological order. So (since $s$ and $t$ must always be included) there are at most $2^{n-2}$ paths.

This bound is tight, for a complete DAG (one in which every pair of vertices is connected by an edge, oriented consistently with a single topological order).


---

