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.

  • $\begingroup$ 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)? $\endgroup$ – Gerry Myerson Mar 1 '13 at 11:35

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.


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.