# 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 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). – hotadvice May 8 at 20:57

[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

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. – Calvin Lin Jan 23 '13 at 2:26
It is a simple graph. What I mean is essentially a Kripke structure, but without looping. – william007 Jan 23 '13 at 2:31