Maximum number of path for acyclic graph with start and end node

Say given an acyclic graph with n nodes, which includes a starting node s0 and ending node e0, what is the maximum number of path from s0 to e0?

• If it's acyclic, how can there be more than one? Or do you mean a directed graph? Jan 23, 2013 at 2:19
• Yes, it is directed acyclic graph. Jan 23, 2013 at 2:28

If you want the maximum number for any graph (of some size), that's easy. Take the maximal graph with N vertices $v_1...v_n$ where $v_1$ is $s_o$ and $v_n$ is $e_o$, with edges $v_i \rightarrow v_j$ for all $1 \le i < j \le n$. Now any sequence $v_1v_{p_1}...v_{p_k}v_n$ where $1 < p_1 < p_2 < ... < p_k < n$ is a path from $s_0$ to $e_0$. Or to put it another way, any subset of the vertices which includes both $s_0$ and $e_0$ uniquely defines a path (by sorting the vertices into index order); there are $2^{n-2}$ such subsets.

If you have a specific graph, then you can use the following procedure to compute the number of paths:

1) Topologically sort the vertices. The first vertex in the topological sort must be $s_0$ and the last one must be $e_0$ (unless I misunderstand your question; if so, just use the portion of the topological sort between the start and end vertex.)

2) Associate a count with each vertex. Set the count associated with $e_0$ to be 1.

3) For each vertex in the topological sort in reverse order, starting with the vertex just before $e_0$, set its count to the sum the counts of all of its neighbour vertices.

4) The count associated with $s_0$ is the total number of possible paths.

You don't actually have to do the topological sort. You can just depth-first-search the tree starting with $s_0$, computing the counts recursively.

• If possible, could elaborate more on how the total paths sum to.... 2 to the power (n-2). May 8, 2016 at 20:57
• There are n-2 vertices (excluding start and end vertex). Each of this could either be on a chosen path or not. Hence, there is 2 to the power (n−2) paths
– nave
Apr 17, 2018 at 16:15

1- Finding the Number of Subsets of a Set

Let's start with stating the obvious: Every path from start to end must contain the start and end nodes and can include as many or as less nodes in between. In other words, its a given that the start and end nodes are included in the path, so we play around with the remaining (N-2) nodes. In set theory lingo that translates to: For a DAG that has N-2 intermediate nodes. Any number of these nodes can be included. How many different paths are possible?

C(N-2, 0) + C(N-2, 1) + C(N-2, 2) + C(N-2, 3) + ....... + C(N-2, N-2)

For simplicity, let n = N-2

C(n, 0) = How many ways we can choose zero intermediate nodes between start and end = n!/(n-k)! * k! = n!/(n! * 0!) = 1 C(n, 1) = How many ways we can choose 1 intermediate nodes between start and end ... etc

Below is a visual illustration of the possible paths for a sample DAG:

visual explanation 1

2- Children and chairs

Another way to find the upper limit mathematically is as follows: For each one of the intermediate nodes (excluding start and end node) there is one of two options: Either be part of the path, or no. This can be expressed as follows: If we have 3 intermediate nodes, we can treat them as chairs. 2 * 2 * 2 = 2^3 = 8 paths

visual description 2

K = number of paths = 2^(N-2)

Time comlexity = E + k*V = E + 2^(N-2)*V, where E = number of Edges, V = number of vertices

• That visual explanation is awesome thanks +1 Nov 19, 2021 at 15:47

I suppose the graph is connected, otherwise there might be no path at all. In general there are infinitely many paths starting from s0 and ending in e0 if you not require them to be simple. If you require them to be simple there is only one.

• Doesn't an undirected cyclic graph disallow self loops and multi edges? Otherwise, you can form a cycle. Jan 23, 2013 at 2:26
• It is a simple graph. What I mean is essentially a Kripke structure, but without looping. Jan 23, 2013 at 2:31