Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let's consider a directed graph with positive edge weights. For every vertex we determine the difference

D = (summary weight of edges directed FROM this vertex)-(summary weight of edges directed INTO this vertex).

We are given the difference D for every vertex. Sum of all the D's is always 0. What is the best algorithm of finding a graph connecting those vertexes, with minimum number of edges.

If this is not clear, there's an example: we have three vertexes and differences for them: D_A = 5, D_B = -20, D_C = 15 (total = 0).

Solution (the best graph connecting those vertexes) would consist of two edges: A--(5)-->B, C--(15)-->B, and it satisfies all the conditions. This example is trivial, but I believe that solution to this problem in general is not simple at all.

share|improve this question
    
There is some requirement you are not stating. You don't just want the minimum number of edges, but you want --- what? --- the maximum sum of weights on the edges (consistent with the $D$-values)? –  Gerry Myerson Mar 1 '13 at 11:35

1 Answer 1

up vote 2 down vote accepted

First, divide the vertex weights into a maximum number of portions that each sum to 0 and handle them separately.

For each set of vertices whose weights sum to 0, you can can implement them as a path with edges forward or backward. Just arrange them in arbitrary order and decide one edge at a time. For example for $a=2, b=-3, c=-4, d=6, e=-1$, use order $a-b-c-d-e$, then you can set $a\to b$ weight 2, $c\to b$ weight 1, $d\to c$ weight 5, $d\to e$ weight 1. There is no way to go wrong.

So the answer is the number of vertices minus the maximum number of parts the weights can be divided into such that each part sums to 0.

share|improve this answer

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.