# 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? –  Robert Israel Jan 23 '13 at 2:19
Yes, it is directed acyclic graph. –  william007 Jan 23 '13 at 2:28

[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$.

-
Hi, Thanks, but I do not quite understand the explanation, maybe possible with a simple example? Say given 10 nodes, what will be the maximum number? The graph can be any graph satisfying kripke structure without looping. Kripke structure is just a structure with start and end node with directed edge in between. –  william007 Jan 23 '13 at 2:41

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.

-