Min spanning tree that preserves total weight of original graph
Let us represent the people involved by numbers $1,\ldots,n$. For person $i$, let $\delta_i$ be the total amount that person $i$ is owed minus the total amount that she owes; notice that $\sum_{i=1}^n \delta_i = 0$. After all transactions have cleared, the capital of person $i$ should change by $\delta_i$. I will now show how to implement this scheme using at most $n-1$ transactions, using an iterative procedure.

If all $\delta_i$ are zero then no transactions need to be done, so we can assume that there exists some non-zero $\delta_i$. Let $i$ be a person such that $|\delta_i|$ is minimal. Since the $\delta_i$ sum to zero, there must be some $\delta_j$ with opposite sign. By our choice of $\delta_i$, $|\delta_j| \geq |\delta_i|$. If $\delta_i &gt; 0$ then we tell person $j$ to pay person $i$ the amount of $\delta_i$, and if $\delta_i &lt; 0$ then we make the opposite transaction. We update the $\delta$ vector accordingly: $\delta_i := 0$ and $\delta_j := \delta_j + \delta_i$ (maintaining the invariant that the $\delta_i$ sum to zero), and continue to the next iteration. In each iteration we zero out at least one $\delta_i$, so in iteration $n-1$ there will be at most two non-zero $\delta_i$, which will both be zeroed during the iteration (since they sum to zero). This shows that there are at most $n-1$ transactions in total.



Minimizing the total number of transactions is NP-hard, by reduction from the following problem:


  Given $n$ numbers in the range $[-n,+n]$ summing to zero and an integer $k$, can the numbers be partitioned into $k$ sets summing to zero?


This problem is shown to be NP-hard on math.se.

We will reduce this problem to the following:


  Given an owe graph and an integer $\ell$, can the graph be implemented using at most $\ell$ transactions?


Suppose that we are given a list of $n$ numbers $x_1,\ldots,x_n$ summing to zero and an integer $k$. Running the algorithm above, we construct an owe graph in which $\delta_i = x_i$. I claim that this owe graph can be implemented using $n-k$ transactions iff the list can be partitioned into $k$ parts summing to zero.

Suppose first that the list can be partitioned into $k$ parts summing to zero. Running the algorithm above for each of the parts, we end up with $n-k$ transactions. Conversely, suppose that the graph can be implemented using $n-k$ transactions. Thought of as a graph, these support at least $k$ connected components, each of which corresponding to a list summing to zero.