The problem
A loan graph is a directed weighted graph $\mathcal{G} = (V, A),$ where $A \subseteq V \times V.$ If we have a directed arc $(u, v)$, we interpret it as the node $u$ gave a loan of $w(u, v)$ money units to the node $v$. Now, suppose all debtors want to pay all their debts at the same instant. Even if we disallow self-loops, a loan graph may have as much arcs (loans) as $n^2 - n$. Since paying back every debt requires both time and energy, what we want to do is to find an isomorphic graph $\mathcal{G}'$ with as little arcs as possible.
Before we define the concept of loan graph isomorphism, we need to define the equity function:
$$e(u) = \sum_{(u, v) \in A} w(u, v) - \sum_{(v, u) \in A} w(v, u).$$
Or in other words, an equity of a node is the sum of the loans it gave minus the sum of debts it has.
Now, two loan graphs $\mathcal{G} = (V, A)$ and $\mathcal{G}' = (V, A')$ are isomorphic if and only if there exists a bijection $f \colon V \to V$ such that $e(u) = e(f(u))$ for all $u \in V$.
There is a trivial algorithm that guarantees no more than $n - 1$ directed arcs in the result graph: split $V$ into two subsets $V_- = \{ u \in V \colon e(u) < 0 \}$ and $V_+ = \{ u \in V \colon e(u) > 0 \}$. Next, take two pointers for the two subsets: $f_-$ and $f_+$. Create the arc $(V_+[f_+], V_-[f_-]$ and set its weight to $w = \min(|e(V_+[f_+]|, |e(V_-[f_-]|)$. Then subtract $w$ from both the equities of the nodes currently pointed at. Whichever node gets the equity of zero, omit it and go point to the next node in the subset. (Basically, this procedure resembles merging two sorted lists.)
Actually, we need to define a group $\mathfrak{G} \neq \varnothing$ to be a subset of $V$ such that $$ \sum_{u \in \mathfrak{G}} e(u) = 0. $$ A group is proper if and only if there exist no nonempty subset $A \subsetneq \mathfrak{G}$ such that both $A$ and $\mathfrak{G} \setminus A$ are groups.
Since a loan graph with $k$ proper groups can be reconnected with $|V| - k$ arcs, we want to maximize $k$.
At this stage, the problem simplifies to the following:
Given a bunch of numbers that sum to zero, partition them in as many groups as possible.
Question
I would not be surprised if the problem is already studied, yet I have absolutely no idea how it may be called.
So finally, what is the name of the problem I specified?
Algorithm request
As of now, I tried three different algorithms [1]:
- Combinatorial: find a group from input, recur to find out whether it is possible to split it into subgroups, and so on.
- Partitional: generate all partitions of positive and negative lists, and check whether they may be paired into groups.
- Greedy: find as small a group as possible, remove it and repeat the search.
1 and 2 are brute force but exact. 3 is fast whenever there is a large number of small groups. Also, 3 is not optimal in general, yet it is most of the times.
Can you improve any of them?
