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?

Improve this question
$\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$
    – Peter Heinig
    Commented Oct 15, 2017 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$
    – Mikhail Tikhomirov
    Commented Oct 15, 2017 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$
    – Mikhail Tikhomirov
    Commented Oct 15, 2017 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
    Commented Oct 16, 2017 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 [email protected] with details. $\endgroup$
    – Todd Trimble
    Commented Oct 16, 2017 at 17:49

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ What is $\lambda$? Can you please elaborate your answer a bit? $\endgroup$
    – J. Abraham
    Commented Oct 15, 2017 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$
    – Fedor Petrov
    Commented Oct 15, 2017 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
    Commented Oct 15, 2017 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$
    – Mikhail Tikhomirov
    Commented Oct 15, 2017 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$
    – Mikhail Tikhomirov
    Commented Oct 15, 2017 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.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .