5
$\begingroup$

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?

$\endgroup$
7
  • 1
    $\begingroup$ Re "UPD" : according to p. 9 in Naoki Katoh: An ϵ-approximation Scheme for Minimum Variance Combinatorial Problems. International Institute for Applied Systems Analysis Austria. WP-97-117, 1987, the minimum-variance spanning tree [ed.: this is the key technical term] can be solved in time $O(h(V,E)\cdot\lvert V\rvert\cdot\lvert E\rvert)$, where $h(V,E)$ denotes the # of steps required for finding an MST in $G=(V,E)$; and it's known that $h(V,E)\in O(\lvert E\rvert\cdot\min\{ i\in\omega\mid\ i>0,\log^{\circ i}(n)\leq\lvert E\rvert/\lvert V\rvert\})$. $\endgroup$ Oct 15 '17 at 19:00
  • 2
    $\begingroup$ @PeterHeinig The result you are mentioning seems obsolete compared to the $O(|E|^2 \log V)$ solution in my answer. $\endgroup$ Oct 15 '17 at 19:53
  • 1
    $\begingroup$ @J.Abraham Depending on the range of $k$, this may allow to make considerable optimizations. For instance, there is a simple $O(k|V| \alpha(|V|))$ algorithm along the same lines with my answer that uses the fact that there are only $O(k)$ different orders now, and that we can leave only $O(|V|)$ edges of each weight value (here $\alpha(|V|)$ is the inverse Ackermann function used in the disjoint set union data structure necessary for Kruskal's algorithm). $\endgroup$ Oct 15 '17 at 20:10
  • 1
    $\begingroup$ Please do not answer this question until midnight. There is a competition now and this task is one of the problems. $\endgroup$
    – be fair
    Oct 16 '17 at 15:25
  • 1
    $\begingroup$ Apologies for the possible inconvenience, but this question will have to be deleted, pending investigation of its allegedly being a competition problem. @befair Please write moderators@mathoverflow.net with details. $\endgroup$
    – Todd Trimble
    Oct 16 '17 at 17:49
5
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ What is $\lambda$? Can you please elaborate your answer a bit? $\endgroup$
    – J. Abraham
    Oct 15 '17 at 9:11
  • 1
    $\begingroup$ $\lambda$ is a free real parameter, Mikhail uses the formula $\sum (w_i-w)^2=\min_{\lambda} \sum (w_i-\lambda)^2$ (where $w$ is arithmetic mean of $w_i$'s). $\endgroup$ Oct 15 '17 at 10:38
  • $\begingroup$ I understand that if $\lambda$ is fixed then we can use Kruskal's algorithm, but what values should $\lambda$ have? If you could please elaborate, because I don't understand. $\endgroup$
    – J. Abraham
    Oct 15 '17 at 11:53
  • 1
    $\begingroup$ We don't choose actual values of $\lambda$ since we only need the order of edges that corresponds to the optimal value of $\lambda$. There are only so much different orders that correspond to values a $\lambda$, hence if we try each of them, we will find the answer that corresponds to optimal $\lambda$. $\endgroup$ Oct 15 '17 at 12:50
  • 1
    $\begingroup$ @HenrikRüping If there were a better spanning tree $T'$ for a particular $\lambda$, then the functional would be even better with $\lambda$ equal to the mean of edge weights of $T'$, hence the former tree would not be optimal. $\endgroup$ Oct 15 '17 at 20:05
1
$\begingroup$

It seems that Mikhail's nice answer will lead to a solution of the opening poster's problem.

I would like to make one little precise point:

Even in situations where the 'linear' problem of 'minimum-weight-spanning tree' has a unique solution, the problem of the opening poster (of finding a spanning tree with minimum quadratic deviation need not have a unique solution. (As proved by the following explicit counterexample, which probably is the 'smallest counterexample', in a reasonably loose sense of 'smallest').

Consider the undirected connected and (edge-)weigted multigraph (which happens to be a simple graph)

enter image description here

enter image description here

This completes the counterexample.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.