Min spanning tree that preserves total weight of original graph

I have a directed, weighted graph with no double edges. Each node represents a person, and each edge represents a debt. I want to reduce the total number of transactions required to settle all debt, i.e. have the smallest number of edges while maintaining fairness.

I've noticed that you can eliminate edges when you owe person A who owes person B, but you also owe person B. Therefore, you can take on the debt of A directly, reducing the size of the graph to two edges instead of 3:

ME                   ME
  /  \                 /  \
 /    \               /    \
B    B      A

(ME points to A and B)

I'm having trouble coming up with a general approach for this, and I'm not sure what to google since this is an unusual use of spanning tree.

I've thought about building up the graph one edge at a time, then analyzing what simplifications can be made, but the build order seems to matter and often does not produce the most optimal graph.

Edit: formalized constraints

There is a set of individuals $p$ that may owe each other money. For any pair $(p_i, p_j)$, if they owe each other money, it is one directional, i.e. $p_i$ cannot owe money to $p_j$ if $p_j$ owes money to $p_i$.

You are given a list with entries $p_x \to p_y, n$ where $n \in R$. This means that $p_x$ owes $p_y$ $n$ amount of dollars.

Your goal is to return a list of identical form with the following constraints:

• It is fair in the sense that each individual in $p$ incurs a wealth difference as if the transactions in the original list were performed.

• It is the shortest such list possible

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 > 0$ then we tell person $j$ to pay person $i$ the amount of $\delta_i$, and if $\delta_i < 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.

StackExchange Computer Science Q#79589, answer score: 4