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