Let $G = \langle V, E \rangle$ be an undirected, connected and weighted multigraph, with the weights given by a function $w: E \rightarrow N$. Consider any spanning tree $T$. Denote the edges of $T$ by $e\_1, e\_2, \ldots , e\_{|V|-1}$. Define $P\_T = \frac{\sum\_{i = 1}^{|V| - 1|} w(e\_i)}{|V| - 1}$, the arithmetic mean of weights of edges in $T$. Define $F\_T = \sum\_{i = 1}^{|V| - 1|} (w(e\_i) - P\_T)^2$. I want to find a spanning tree $T$ which minimizes $F\_T$. Is there any known polynomial time algorithm for this problem?


**UPD:** What is the fastest algorithm that can solve it?



Spanning tree minimizing $F_T = \sum_{i = 1}^{|V| - 1|} (w(e_i) - P_T)^2$
The problem is equivalent to finding $\min\_{e\_i, \lambda} \sum (w(e\_i) - \lambda)^2$, where $\lambda$ is a free real parameter subject to optimization as well as the edges of a spanning tree. Indeed, for a chosen set of edges $e\_i$ we have that $\sum (w(e\_i) - \lambda)^2$ is minimized when $\lambda$ is the mean of $w(e\_i)$.


If $\lambda$ is fixed, we can use, say, Kruskal's algorithm which considers edges by increasing of $|w(e) - \lambda|$. Note that if we gradually increase $\lambda$, the order of edges only changes at $\lambda = (w(e) + w(e')) / 2$ for some edges $e, e'$, therefore there are polynomially many different orders. Run Kruskal's algorithm with respect to each of these orders and choose the best answer.


The complexity is roughly $O(|E|^3)$ if done straightforwardly. **UPD**: This approach can be optimized to $O(|E|^2 \log |V|)$, roughly as follows: when we process a "two edges $e\_1$, $e\_2$ switch their order to $e\_2$, $e\_1$" event, the result of the Kruskal algorithm changes iff all edges on the cycle of the current MST induced by $e\_2$ are $\geq e\_1$, then we have to delete $e\_1$ and insert $e\_2$. This can be done efficiently with link-cut trees.


