algorithm to determine minimum payments amongst a group

Question

The Problem

I was recently asked to calculate the money owed amongst a group of people who went on a trip together and came upon an interesting problem: given that you know the amounts that each person owes another, what is a general algorithm to consolidate the debts between people so that only the minimum number of payments needs to be made? Take this as an example:

• Mike owes John 100
• John owes Rachel 200
• Mike owes Rachel 400

We can remove a payment between Mike and John by reformulating the debts like this:

• Mike owes John 0
• John owes Rachel 100
• Mike owes Rachel 500

I did the math by hand since it was easy enough, but then the programmer in me was itching to figure out a general algorithm to do it for an arbitrarily large group. This seems like a graph algorithm to me, so I'll reformulate this as a graph:

Viewed as a Graph

• The vertices are the people in the group
• The edges are directed and weighted by the amount owed. For example, an edge from Mike to Rachel with weight 500 means that Mike owes Rachel 500.
• Constraint: the net sum of weights for each node must remain unchanged.
• The goal is to find a graph with the minimum number of edges that still satisfy the constraint.

Answer 1

It does not suffice to just figure out the receivers and givers. While I think this strategy is on the right track it also does not ensure an algorithm to find the least possible amount of payments.

For Example,

• Person A owes 25
• Person B owes 50
• Person C owes 75
• Person D is owed 100
• Person E is owed 50

While it is obvious that this can be done in 3 pays (A and C to D, B to E). I can't think of an efficient algorithm that will satisfy this for all problem sets.

Better Example,

• Person A owes 10
• Person B owes 49
• Person C owes 50
• Person D owes 65
• Person E is owed 75
• Person F is owed 99

If we took the greedy approach of having person D pay to F we would wind up with a sub-optimal solution as opposed to the optimal(A&D to E, B&C to F).

This problem has a lot of similarity with the Bin Packing Problem which has been proven to be NP-hard. The only difference being that we have multiple bins of varying sizes and the condition that the total space in all bins is equal to the total size of all items. This leads me to believe that the problem is likely NP-hard but with the added constraints it may be possible to solve in polynomially time.