1

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 :)

Iago Carvalho
  • 185
  • 1
  • 2
  • 9
  • 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 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 Apr 10 '19 at 20:06
  • You didn't get their reduction right... – Yota Otachi Apr 11 '19 at 00:58

1 Answers1

12

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

David Eppstein
  • 50,990
  • 3
  • 170
  • 278