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