Minimal Spanning Tree With Double Weight Parameters

Question

Consider a graph $G(V,E)$. Each edge $e$ has two weights $A_e$ and $B_e$. Find a spanning tree that minimizes the product $\left(\sum_{e \in T}{A_e}\right)\left(\sum_{e \in T}{B_e}\right)$. The algorithm should run in polynomial time with respect to $|V|, |E|$.

I find it difficult to adapt any of the traditional algorithms on spanning trees(Kruskal, Prim, Edge-Deletion). How to solve it? Any hints?

Answer 1

I'm going to assume you are not given negative weighted edges, because this may not work if there are negative weights.

Algorithm

For each of your edges, label them $1$ to $n$

Let $a_i$ weight A of edge number $i$

Let $b_i$ weight B of edge number $i$

Draw up this table

   |a_1 a_2 a_3 a_4 .. a_n
---+-------------------------
b_1|.........................
b_2|.........................
 . |.........................
 . |.........................
b_n|...................a_n * b_n

With each of the table elements being the product of row and column.

For each edge, sum the relevant table row and column (and remember to remove the element in the intersection since it has been summed twice).

Find the edge that has the largest sum, delete this edge if it doesn't disconnect the graph. Mark the edge as essential otherwise. If an edge has been deleted, fill its rows and columns with 0.

Correctness

The result is obviously a tree.

The result is obviously spanning since no vertices are disconnected.

The result is minimal? If there is another edge whose deletion will create a smaller spanning tree at the end of the algorithm, then that edge would have been deleted and nulled first. (if somebody could help me make this a bit more rigorous/and/or counter example then that would be great)

Runtime

Obviously polynomial in $|V|$.

edit

$(2,11), (11,2), (4,6)$ is not a counter example.

$a_1 = 2, a_2 = 11, a_3 = 4$

$b_1 = 11, b_2 = 2, b_3 = 6$

Then

   | 2     11     4
---+--------------------
11 | 22    121    44
 2 | 4     22     8
 6 | 12    66     24

\begin{align*} (4,6) &= 44 + 8 + 24 + 66 + 12 = 154 \\ (2,11) &= 22 + 4 + 12 + 121 + 44 = 203 \\ (11,2) &= 121 + 22 + 66 + 4 + 8 = 221 \end{align*}

$(11,2)$ gets removed.

End up with $(2,11), (4,6) = 6 * 17 = 102$

Other spanning trees are

$(11,2), (4,6) = 15 * 12 = 180$

$(2,11), (11,2) = 13 * 13 = 169$

Answer 2

This is the solution from http://www.cnblogs.com/autsky-jadek/p/3959446.html.

We can view every spanning tree as a point in the $x-y$ plane, where $x$ is the sum of weight $\sum_{e\in T}A_{e}$, y is the sum of weight $\sum_{e\in T}B_{e}$. The goal is to minimize $xy$.

1. Find the minimum spanning tree according to weight $A$ and weight $B$. So we have two points in the x-y plane $A,B$. In all of the spanning tree points in the plane, $A$ has the minimum $x$, $B$ has the minimum $y$.

2. Now we aim to find a point $C$ in the triangle $OAB$ that has maximum distance to line $AB$, so that we can have the $xy$ value for $C$ minimized for all points in triangle $ABC$.

Because $2S_{ABC}=|\overrightarrow{AB}\times\overrightarrow{AC}|=(B_{x}-A_{x},B_{y}-A_{y})\times(C_{x}-A_{x},C_{y}-A_{y})=(B_{x}-A_{x})\cdot C_{y}+(A_{y}-B_{y})\cdot C_{x}-A_{y}(B_{x}-A_{x})+A_{x}(B{}_{y}-A_{y})$.

3. Notice that $A_{y}(B_{x}-A_{x})+A_{x}(B{}_{y}-A_{y}$ is a constant, so now we are aiming to maximize $(B_{x}-A_{x})\cdot C_{y}+(A_{y}-B_{y})\cdot C_{x}$. So we make a new graph $G^{\prime}=(V,E)$, while the weight $w(e)=B_{e}(B_{x}-A_{x})+C_{x}(A_{y}-B_{y})$. Now we run a maximum spanning tree on $G^{\prime}$ to get point $C$.

4. Run the above algorithm on $OBC, OAC$ recursively, until there is no more spanning trees between $BC,AC$ and $O$.

5. Now we get a set of possible spanning trees. Calculate $xy$ value for each tree to get the minimum tree.