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.

Answer 2

It might be inefficient, but you could use Integer Programming.

Precompute net flow into/out of node i, i.e. Fi = total debts + total credits

Let M be a large number.

Let Yij be decision variable denoting amount node i pays to node j (ordered pairs).

Let Xij be binary variable to indicate that a transaction took place between i & j (unordered pairs)

Optimize the following:

min sum_{i,j} Xij

sum_{j!=i} Yij = Fi

Yij + Yji= <= M*Xij

Answer 3

You can try the greedy method. So

If A owes money to B and B owes C then A owes C the minimum of (A->B, B->C). And A->B -= min(A->B, B->C). If after this operation A->B becomes zero then you remove it. Loop till you cannot perform any further operation ie, there're no cycles in the graph.:

do{
    bool stop = true;
    G.init() // initialize some sort of edge iterator
    while(edge = G.nextedge()){  //assuming nextedge will terminate after going through all edges once

        foreach(outedge in edge.Dest.Outedges){ //If there's any node to 'move' the cost
            minowed = min(edge.value, outedge.value)
            G.edge(edge.Src, outedge.Dest).value += minowed
            edge.value -= minowed
            outedge.value -= minowed
            if(edge.value == 0) G.remove(edge)
            if(outedge.value == 0) G.remove(outedge)
            stop = false
        }
    }
}while(!stop)

This amounts to basically removing any cycles from a graph to making it a DAG.