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

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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.