Say you have n people, each who owe each other money. In general it should be possible to reduce the amount of transactions that need to take place. i.e. if X owes Y £4 and Y owes X £8, then Y only needs to pay X £4 (1 transaction instead of 2).
This becomes harder when X owes Y, but Y owes Z who owes X as well. I can see that you can easily calculate one particular cycle. It helps for me when I think of it as a fully connected graph, with the edges being the amount each person owes.
Problem seems to be NP-complete, but what kind of optimisation algorithm could I make, nevertheless, to reduce the total amount of transactions? Doesn't have to be that efficient, as N is quite small for me.
Edit:
The purpose of this problem would be to be able to have in the accounting system something that can say to each person when they log in "You can remove M amount of transactions by simply paying someone X amount, and someone else Y amount". Hence the bank solution (though optimal if everyone is paying at the same time) cannot really be used here.