title: Who owes who money optimization
body: <p>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).</p>
  
  <p>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.</p>
  
  <p>Problem seems to be NP-complete, but what kind of optimisation algorithm could I make, nevertheless, to reduce the <strong>total</strong> amount of transactions? Doesn't have to be that efficient, as N is quite small for me.</p>
  
  <p>Edit:</p>
  
  <p>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.</p>