# Number of simple paths between two vertices in a DAG

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) and that is an enumeration problem. This algorithm is #P-Complete on general digraphs, but is in $$P$$ for DAGs, as pointed out by @Joshua Grochow in the comments.

I'm also aware that this number is exponential on the size of the longest $$s-t$$ path.
However, I don't see a relation between this function and the number of nodes in the graph.

Thanks in advance :)

• 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 Apr 10 '19 at 18:51
• 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 Apr 10 '19 at 18:54
• 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 Apr 10 '19 at 19:34
• OK, I accept that. This question came in my mind because such a structure was used within an NP-Hard proof. See the article citeseerx.ist.psu.edu/viewdoc/… (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 Apr 10 '19 at 20:06
• You didn't get their reduction right... – Yota Otachi Apr 11 '19 at 0:58

## 1 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).