8
$\begingroup$

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]:

  1. Combinatorial: find a group from input, recur to find out whether it is possible to split it into subgroups, and so on.
  2. Partitional: generate all partitions of positive and negative lists, and check whether they may be paired into groups.
  3. 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?

$\endgroup$
  • 1
    $\begingroup$ The number grouping problem is very similar to 3-Partition, and is strongly NP-hard by reduction from it. $\endgroup$ – Tom van der Zanden Apr 18 '16 at 8:40
  • 1
    $\begingroup$ 1. The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. 2. "What is the name of this problem?" is rarely a good question. There are many more problems without names than problems with names. That's the great thing about language; it enables us to describe an unlimited number of problems, even ones that maybe no one has ever thought of before. It's better to ask an answerable, technical question, (cont.) $\endgroup$ – D.W. Apr 18 '16 at 17:06
  • $\begingroup$ such as "Is there an efficient algorithm for this problem?" or "Is this problem NP-hard?" or "is there an approximation algorithm for this problem?" I suggest you edit the question accordingly. Make sure to show us what approaches you've considered so far and what you've come up with so far (you have tried thinking about solutions to it before asking, right?). $\endgroup$ – D.W. Apr 18 '16 at 17:08
  • $\begingroup$ cs.stackexchange.com/q/1240/755 $\endgroup$ – D.W. Apr 18 '16 at 17:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.