Minimizing the amount of bank transactions in a static loan graph


Suppose we are given a directed, weighted graph \mathcal{G} = (V, A), where V is the set of nodes, and A \subseteq V^2 is the set of directed arcs. Also we are given a weight function w \colon A \to \mathbb{R}_{> 0}. We interpret each graph node as an entity in a financial graph, or namely, each node models a bank, a company or an individual. Whenever we are given a directed arc (u, v) \in A, u is the creditor, v is the debtor and w(u, v) > 0 is the amount of resource units being owed. We call such a graph a loan graph.

We will need the following function denoting equity of a node:

\displaystyle e_{\mathcal{G}}(u) = \sum_{(u, v) \in \mathcal{G}.A} w(u, v) - \sum_{(v, u) \in \mathcal{G}.A} w(v, u).

Definition

Two loan graphs \mathcal{G}_1 = (V, A_1) and \mathcal{G}_2 = (V, A_2) are said to be isomorphic, if and only if there exists a bijection f \colon V \to V, such that e_{\mathcal{G}_1}(u) = e_{\mathcal{G}_2}(f(u)) for all u \in V.

Now, given a loan graph \mathcal{G}, we want to compute another loan graph that is isomorphic to \mathcal{G} and has the minimum amount of arcs needed to preserve the equities.

Definition

A subset of nodes V' is a group if and only if

\displaystyle \sum_{u \in V'} e(u) = 0.

A trivial group is a single node u with e(u) = 0. A semi-trivial group is a pair of nodes \{ u, v \} such that e(u) \neq 0 \neq e(v) and e(u) = -e(v). Any other group is a non-trivial group. A group V is said to be proper, if there exists no \mathfrak{G} \subsetneq V, such that \mathfrak{G} \neq \emptyset and \mathfrak{G} and V - \mathfrak{G} are groups. A group is said to be improper if it is not a proper group. Note that only non-trivial groups may be improper.

Whenever we construct a loan graph by adding weighted arcs, upon each arc with weight w, we increase the equity of one node by w and we decrease the equity of another node by the same amount, which implies that every loan graph is a group. Also, every group V may be reconnected in linear time with at most |V| - 1 arcs. Note that it is a large improvement whenever A = \Theta(V^2) as in the case of dense loan graphs.

In order to construct a minimal loan graph (i.e., the loan graph with the least possible amount of arcs), we need to find the maximal amount of proper groups. We say maximal, as it is possible (in some cases) to produce a partition, whose each block constitute a proper group, but the amount of groups is not maximal. Partitions into proper groups are not necessarily unique, and if they aren’t, there is no guarantee that all such partitions will imply the same amount of arcs, as is demonstrated in the following example: Suppose we have a loan graph of six nodes, with equity sequence \langle -4, -2, -2, 2, 2, 4 \rangle. Now there is two ways such a loan graph may be partitioned into proper groups:

  1. \langle -4, 2, 2 \rangle \langle-2, -2, 4 \rangle
  2. \langle -2, 2 \rangle \langle -2, 2 \rangle \langle -4, 4 \rangle

Note that the first partition produces four arcs, and the second one produces three. In general, a loan graph with n nodes and m groups may be reconnected with only n - m arcs.

It is clear that the minimal loan graph problem is combinatorial. Therefore there might be need for speeding the computation by reducing the size of the problem instance. For example, before doing the search, we might discard trivial and semi-trivial groups, thus reducing the size of the input problem isntance. It seems like a greedy strategy, and we know that greed does not always lead to optima. Notwithstanding, the following lemma proves that discarding trivial and semi-trivial groups before the computation does not necessarily lead to suboptimal solution:

Lemma

Discarding trivial and semi-trivial groups from the input does not imply suboptimality of the solution.

Proof
Suppose the maximum amount of groups in the input graph is n, n_1 of which are trivial groups, and n_2 of which are semi-trivial groups. Now suppose the contrary: discarding all the trivial and semi-trivial groups leads to suboptimal amount of total groups, n'. By definition of suboptimality, we must have that n - n_1 - n_2 > n', which is absurd since n' = n - n_1 - n_2.

Since there seems no way of validating the optimality of a solution in polynomial-time, the loan graph problem seems to be NP-hard; to be verified in future posts.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s