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?
 A: 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.
A: 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
A: This is wrong.

[If it's not a directed graph, then there is at most 1 path between any 2 vertices, otherwise we will have a cycle.]
A directed acyclic graph can be divided into several sets of vertices $V_1, V_2, \ldots V_k$ such that each edge leads from $V_i$ to $V_{i+1}$.
You can easily see that the number of such paths is going to be capped at $|V_2| \times |V_3| \times \ldots |V_{k-1}|$, since the path must have the form $s_0, v_2, v_3, \ldots v_{k-1}, e_0$ for $v_i \in V_i$. This becomes a number theory problem, where we want to partition $n-2$ to maximize their product.
Verify that $2 \times 2 \times 3 < 3 \times 3$, and $3^n \geq n^3$ for $n \geq 3$. Hence, we want to maximize the number of 3's in the sequence. There will be slight differences according to $n-2 = 3k, 3k+1, 3k+2$, and also possibly for small values of $n$.
A: 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.
