# Minimal Spanning Tree With Double Weight Parameters

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?

• Maybe try to construct a new graph, where the weight of an edge $e$ is $\max(A_e,B_e)$. Sep 24, 2012 at 8:12
• Is this a homework problem / exercise? If so, is it from a textbook? The reason I ask is that context can help to "reverse-engineer" the problem. It's not immediately obvious that a greedy algorithm is appropriate here, but if it comes from the chapter on greedy algorithms...
– Joe
Sep 25, 2012 at 1:00
• @utdiscant, that wont work. Negative edges may be useful. Sep 26, 2012 at 23:25
• even for positive edges is not useful, e.g pair (10,10) is not better than pair (11,1) in most cases.
– user742
Nov 13, 2012 at 15:02

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$

• It seems to me, that this is a rather greedy aproach. I am not convinced by your "proof" of minimalism.
– Nejc
Nov 13, 2012 at 15:22
• @SaeedAmiri How is that a counter example? I posted the working in the edited section, the algorithm gives the correct result. Nov 14, 2012 at 4:49
• What you did is finding how much each $(a _i, b _i)$ contributes in $\sum _{e \in E} a _i. \sum _{e \in E} b _i$, and you pick the ones that have the most impact. That is good, but it is not what is required. It is a tricky question. If you want to improve your answer, you need to come with a proof. Otherwise, there is no use.
– AJed
Nov 14, 2012 at 5:43
• it is very unfair to get a down vote for your effort though.
– AJed
Nov 14, 2012 at 5:44
• @AJed The proof is just the same as in the prim/kush/reverse delete. All we have to prove now is that the cut property still holds. Nov 14, 2012 at 6:01

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})$.

1. 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$.

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

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