0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Joshua Grochow Apr 10 at 18:51
  • $\begingroup$ 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$. $\endgroup$ – Iago Carvalho Apr 10 at 18:54
  • $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Apr 10 at 19:34
  • $\begingroup$ 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. $\endgroup$ – Iago Carvalho Apr 10 at 20:06
  • $\begingroup$ You didn't get their reduction right... $\endgroup$ – Yota Otachi Apr 11 at 0:58
10
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.