# 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 <--- A     ====>   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
• I'm not entirely sure, but possibly strongly connected components could help reduce a SCC to a single debt. Then you would be left with a DAG of debts. Might be worth looking into. – ryan Aug 1 '17 at 21:55
• Also, after removing (A->B) shouldn't (or couldn't) the edge (A->ME) now be present if A owes ME a difference between A's debt to B and ME's debt to A? – ryan Aug 1 '17 at 22:01
• It depends on whether (ME -> A) is less than or greater than (A -> B). In either case, you can reduce the edge count by one, so I left this out for clarity. The example above is in the case of (ME -> A) > (A -> B) – jeanluc Aug 1 '17 at 22:13
• @ryan I looked into strongly connected components and it seems like, by definition, there will be none in my graph. Wikipedia says this about them "... if there is a path in each direction between each pair of vertices of the graph". However, my graph has no double edges. – jeanluc Aug 1 '17 at 22:50
• @jeanluc An oriented triangle (three vertices $a,b,c$ with edges $a\to b$, $b \to c$, $c \to a$) is strongly connected without having opposing edges. – Yuval Filmus Aug 1 '17 at 23:04

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.

• While this is an insightful answer, it is not entirely what I'm looking for. For example, one can take your idea further and solve everything in 2 transactions: Everyone who owes money places that amount in a common pool. Then everyone takes out how much they are owed. – jeanluc Aug 1 '17 at 23:12
• But I want to be able to generate a list from the graph, i.e. A owes B x money, B owes C y money, such that debts can be settled individually. I probably should add this constraint to the question. – jeanluc Aug 1 '17 at 23:13
• I suggest you modify your question by formally stating what you're looking for. Write all constraints you are interested in. – Yuval Filmus Aug 1 '17 at 23:13
• My answer gives a list of $n-1$ transactions of the form A owes B an amount x, which together are equivalent to the original graph. – Yuval Filmus Aug 1 '17 at 23:14
• @jeanluc Finding the minimal number of transactions is NP-hard. – Yuval Filmus Aug 2 '17 at 6:19