# Compute the average path weights of paths with the same path length in a directed acyclic graph (DAG)

Given a weighted directed acyclic graph (DAG) $$G=(V,E)$$ with each edge $$e\in E$$ has a non-negative weight $$w(e)$$. For a path $$p=(e_1,e_2,\dotsc,e_n)$$ in $$G$$, define the path weight as : $$w(p)=\sum_{i=1}^{n}w(e_i)$$, and the path length as: $$\lvert p\rvert=n$$ (number of edges). Define $$\mu(l)=\frac{\sum_{p\in G, \lvert p\rvert=l}w(p)}{\text{number of path with length l}}$$ be the average path weights of paths with the length $$l$$.

We want to compute $$\mu$$ for every $$l\leq \lvert E\rvert$$, is it an NP-hard problem? If not, is there any polynomial-time algorithm that can be used to solve this problem?

• Determining if $\mu(n-1)$ is non-zero is equivalent to the hamiltonian path problem, so it is NP-hard. Dec 21, 2022 at 12:29
• Thanks for the reply! But checking if a Hamiltonian path exists in a DAG is polynomial I guess stackoverflow.com/questions/53743686/…?
– cbyh
Dec 22, 2022 at 13:17
• Sorry, didn't see it was a DAG Dec 22, 2022 at 15:23

We come up with a way to prove this problem to be polynomial, here is the answer (in this answer we talk about the node weights instead of edge weights, but you can easily transfer it to edge weights):

Given a directed acyclic graph $$G=(V,E)$$ with a source node $$s$$ and a sink node $$t$$, and each node $$v\in V$$ has a non-negative weight $$w(v)$$. For a path $$P=\{v_1,v_2,\dots, v_{|P|}\}$$, define the path weight as: $$w(P)=\sum_{i=1}^{|P|}w(v_i)$$, and define $$\mu (l):=\frac{\sum_{P\in G, |P|=l}w(P)}{\sum_{P\in G, |P|=l}1}$$. We want to compute $$\mu(l)$$ for every $$l$$.

We first discuss all the paths that start from the source node $$s$$. We first create a new DAG $$G'$$ with the weight function $$w'$$ according to the following procedures:

(1) Create $$|E|+1$$ layers in $$G'$$, each layer consists of $$|V|$$ nodes, the $$j$$-th node at the $$i$$-th layer, denoted as $$v_{i,j}$$, represents the node $$v_j$$ in $$G$$. Let $$w'(v_{i,j})=w(v_j)$$.

(2)add a source node $$s'$$ in $$G'$$, representing $$s$$ in $$G$$. $$w'(s')=w(s)$$

Now we add edges of $$G'$$.

(1) We do a BFS on $$G$$, start with the source node $$s$$. For each node $$v_i\in V$$ such that there is an edge from $$s$$ to $$v_i$$ in $$G$$, we add an edge from $$s'$$ to $$v_{1,i}$$ in $$G'$$. If $$v_i$$ is not a sink node, then push the pair $$(v_i,1)$$ into the BFS queue.

(2) While the queue is not empty, pop one element out, denoted as $$(v_k,t)$$. For each $$v_i\in V$$ such that there is an edge from $$v_k$$ to $$v_i$$ in $$G$$, we add an edge from $$v_{t,k}$$ to $$v_{t+1,i}$$ in $$G'$$ (easy to see that we always have $$t+1\leq |E|+1$$), and push $$(v_i,t+1)$$ in the queue if $$v_i$$ is not a sink node.

(3)remove all the nodes $$v_{i,j}$$ in $$G'$$ if this node is isolated.

The procedure of creating $$G'$$ is polynomial since $$G'$$ has at most $$(|E|+1)|V|+1$$ nodes and $$|V|^2(|E|+1)$$ edges. Besides, a path from $$s$$ to $$v_i$$ in $$G$$ with length $$l$$ one-to-one corresponds to a path from $$s'$$ to $$v_{l-1,i}$$.

Let $$\mu_{s}(l):=\frac{W_{s}(l)}{N_s(l)}$$ be the average path weights of all paths with the length $$l$$ and the start node $$s$$, $$W_{s}(l)$$ be the sum of path weights of all paths with the length $$l$$ and the start node $$s$$, $$N_s(l)$$ be the number of paths with the length $$l$$ and the start node $$s$$. We now use the graph $$G'$$ to compute these three terms.

(1) For each node in $$G'$$, assign another two values. For $$s'$$, $$(w_{s'},n_{s'})$$, for the other nodes $$v_{i,j}$$, $$(w_{i,j},n_{i,j})$$. $$w_{i,j}$$ represents the sum of path weights of all paths from $$s'$$ to $$v_{i,j}$$ (and of course these paths have length $$i+1$$) and $$n_{i,j}$$ represents the number of such paths.

(2) Denote $$s'$$ as $$v_{0,1}$$, let $$w_{0,1}=w'(s')$$, $$n_{0,1}=1$$.

(3) From lower indexed layer to higher indexed layer, for each $$v_{i,j}$$, let: \begin{align*} w_{i,j}=\sum_{k,v_{i-1,k}\in Par(v_{i,j})}w_{i-1,k}+n_{i-1,k}w(v_{i,j}) \end{align*} where $$Par(v_{i,j})$$ is the set of parent nodes of $$v_{i,j}$$. And: \begin{align*} n_{i,j}=\sum_{k,v_{i-1,k}\in Par(v_{i,j})}n_{i-1,k} \end{align*}

Now we have $$W_{s}(l)=\sum_{j}w_{l-1,j}$$ and $$N_{s}(l)=\sum_{j}n_{l-1,j}$$. Easy to see that this procedure is polynomial.

For each node $$v_i$$ in $$G$$, we can use the same way to generate the new graph and compute $$W_{v_i}(l)$$ and $$N_{v_i}(l)$$. Then: \begin{align*} \mu(l)=\frac{\sum_{v\in V}W_{v}(l)}{\sum_{v\in V}N_{v}(l)} \end{align*} And the total procedure is polynomial.

No need for an external graph, you can use the following recurrence (for edge and vertex weights) which is very similar to yours:

• $$n_v(l)$$ number of paths of length $$l$$ that end at $$v$$
• $$w_v(l)$$ sum of weights of paths of length $$l$$ that end at $$v$$

$$n_v(0) = 1$$ $$w_v(0) = w(v)$$ $$n_v(l) = \sum_{u\in N^-(v)}n_u(l-1)$$ $$w_v(l) = \sum_{u\in N^-(v)}w_u(l-1) + n_u(l-1)w(e_{uv}) + n_v(l)w(v)$$

Compute for each $$v$$ by following a topological ordering of the vertices.

Complexity $$\mathcal{O}([E||V|)$$