Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
Maybe try to construct a new graph, where the weight of an edge $e$ is $\max(A_e,B_e)$. –  utdiscant Sep 24 '12 at 8:12
2  
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 '12 at 1:00
1  
@utdiscant, that wont work. Negative edges may be useful. –  Nicholas Mancuso Sep 26 '12 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 '12 at 15:02
add comment

1 Answer

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$

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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