Lets define the variance of a graph as the variance of its edges' weights. The task I am trying to solve is designing an algorithm which given a graph G will construct a spanning tree T with minimum variance.
I am having a hard time getting the ball rolling on this. So far I've noticed that if the average edge weight in such a spanning tree was known then the problem could be solved by replacing the weight of every edge with the square of its deviation the the average weight and feeding the graph into any MST finding algorithm.
Obviously, I do not know anything about the average edge weight in the tree I am trying to construct, however it occured to me that the average must fall between 2 edges of G and perhaps this information could be exploited.
I'm trying to reduce the problem to finding the MST of G with modified edge weights. I thought about running an algorithm for each edge of G, each time assuming that the initial edge is the closest to average in T and given weight 0 while the other edges get weights equal to the square of their deviation from the weight of the initial edge. This approach went nowhere because if the average isn't equal to the weight of one of the edges, then depending on where it falls between the weights of 2 closest edges the ordering of edges based on their weight would be different and would produce different spanning trees when fed into an MST finding algorithm. This is something I don't know how to handle (or if it even can be handled).
This is homework, so I'd prefer a small hint to send me in the right direction rather than a solution.
Idea 1: You only need to be able to compare edges pairwise when you build a minimum weight spanning tree.
Idea 2:
The pairwise comparison of an edge of weight x and an edge of weight y, when you square the difference between the weights and the guess g, only changes at g=(x+y)/2.
Idea 3:
If there are |E| edges, there are at most (|E| choose 2)+1 essentially different guesses g for the average weight. Compute a minimum weight spanning tree for each of these. Compare the variances of these trees.
There should be much faster ways, but this is a polynomial time algorithm.