What algorithms exist to minimize the number of transactions between nodes in a graph?

Question

That title probably doesn't make sense. Assume the following:

• A owes B $5
• C owes B $10
• B owes D $15

In this basic situation there are three transactions but it can be reduced to two transactions:

• A gives D $5
• C gives D $10

Given a much more complicated graph, what algorithms exist to minimize the total number of transactions?

Answer 1

It seems to me the first thing you have to figure out how much each person is up/down after all transactions take place. For your example, that would be:

A :  -5
B :   0
C : -10
D : +15

Once you have that, you just have to make them all zero. Take your highest gain, and start adding losses to it. At this point it's basically a bin-packing problem.