Suppose we are given a directed, weighted graph , where is the set of nodes, and is the set of directed arcs. Also we are given a weight function . 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 , is the creditor, is the debtor and 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:

.

Two loan graphs and are said to be isomorphic, if and only if there exists a bijection , such that for all .

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

A subset of nodes is a **group** if and only if

A **trivial group** is a single node with . A **semi-trivial** group is a pair of nodes such that and . Any other group is a **non-trivial** group. A group is said to be **proper**, if there exists no , such that and and 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 , we increase the equity of one node by and we decrease the equity of another node by the same amount, which implies that every loan graph is a group. Also, every group may be reconnected in linear time with at most arcs. Note that it is a large improvement whenever 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 . Now there is two ways such a loan graph may be partitioned into proper groups:

Note that the first partition produces four arcs, and the second one produces three. In general, a loan graph with nodes and groups may be reconnected with only 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:

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 , of which are trivial groups, and 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, . By definition of suboptimality, we must have that , which is absurd since .

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.