Find the Minimum Variance Path in Directed Acyclic graph

Question

Given a DAG, in which every node has a numeric value. I would like to obtain the path through the graph which has the minimum variance in the value of the nodes.

To recap, which is the best algorithm to find the minimum variance path in a Directed Acyclic Path?

Thanks, Piero

Answer 1

From the paper: "Routing with Confidence: A Model for Trustworthy Communication"

Definition 6.7. Minimum Variance Simple-Path Problem (MVSPP) : Given a graph G = (V, E), with positive vertex weights w(v) for each vertex v ∈ V , and nonadjacent vertices s, t ∈ V , find an s, t -path p that minimizes the variance of weights for the set of vertices in p .

We assume that s, t are not directly connected by a single edge, because then the solution is trivial. The path 〈s, t〉 has variance 0 and is the minimum variance path.

Theorem 6.8. The Minimum Variance Simple-Path Problem (MVSPP) is NP- hard.

This is what i found out... I think that this answers my question.