August 4th, 2008

beartato phd

(no subject)

Suppose you divide up bills of some kind among n people, and find out that person n owes c_n dollars, c_n being negative if person n is owed money. What is the fewest number of transactions (that is, transfers of money between two people) among the n people that can resolve all these obligations?

I think it's NP-complete via a reduction to the knapsack problem. Any m-sized subset of the original people whose obligations sum to zero can get by with an (m-1)-long chain of transactions, and I think the optimal strategy is to find some partition of the original people into these "balanced" subsets. You shave off one transaction for every such subset, so you want the finest possible partition that works. But finding this partition is NP-hard; take a knapsack problem with weights w_1...w_n with target weight (sum_i w_i)/2 and translate it to a transaction problem with n+2 people, the first n of which owe w_1,...,w_n dollars respectively, and the last two of which are owed (sum_i w_i)/2 each. If there is a subset of the w_i that sums to exactly (sum_i w_i)/2, we can have them pay one creditor (call it k transactions), and their complement of them among the owers can pay the other (n-k transactions) for a total of n transactions.

Otherwise, the graph of transactions has to be connected since there is no subset that sums to zero (as any connected component of that graph would have to) so the fewest edges that can connect a graph of n+2 vertices is n+1.

Thus the question of whether there is an n-transaction way of resolving all debts among n+2 people is NP-hard; plainly it's in NP.