12
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Maybe try to construct a new graph, where the weight of an edge $e$ is $\max(A_e,B_e)$. $\endgroup$ – utdiscant Sep 24 '12 at 8:12
  • 3
    $\begingroup$ 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... $\endgroup$ – Joe Sep 25 '12 at 1:00
  • 1
    $\begingroup$ @utdiscant, that wont work. Negative edges may be useful. $\endgroup$ – Nicholas Mancuso Sep 26 '12 at 23:25
  • $\begingroup$ even for positive edges is not useful, e.g pair (10,10) is not better than pair (11,1) in most cases. $\endgroup$ – user742 Nov 13 '12 at 15:02
1
$\begingroup$

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$

$\endgroup$
  • 1
    $\begingroup$ It seems to me, that this is a rather greedy aproach. I am not convinced by your "proof" of minimalism. $\endgroup$ – Nejc Nov 13 '12 at 15:22
  • 1
    $\begingroup$ @SaeedAmiri How is that a counter example? I posted the working in the edited section, the algorithm gives the correct result. $\endgroup$ – Herp Derpington Nov 14 '12 at 4:49
  • 1
    $\begingroup$ 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. $\endgroup$ – AJed Nov 14 '12 at 5:43
  • $\begingroup$ it is very unfair to get a down vote for your effort though. $\endgroup$ – AJed Nov 14 '12 at 5:44
  • $\begingroup$ @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. $\endgroup$ – Herp Derpington Nov 14 '12 at 6:01
1
$\begingroup$

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.

$\endgroup$

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.