1
$\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 :)

Improve this question
$\endgroup$
5
  • $\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, 2019 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, 2019 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, 2019 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, 2019 at 20:06
  • $\begingroup$ You didn't get their reduction right... $\endgroup$
    – Yota Otachi
    Apr 11, 2019 at 0:58

1 Answer 1

Reset to default
12
$\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).

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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