Adapted from a chapter of my undergraduate dissertation, “Solving Financial Problems using Algorithmic Graph Theory” (2013).

The Problem

Debt is an obligation owed by one party (the debtor) to pay another party (the creditor) some prespecified asset: currency, a product, or an intermediate good. In a financial system many such relations exist at once, and a single entity can be both a debtor to one party and a creditor to another. Unresolved debt has consequences for everyone involved, so we would like to simplify the debt relations as far as possible.

Let $V$ be the set of parties, modelled as a directed graph. An edge $e(v_i, v_j) \in E$ annotated with $d_{ij} \in \mathbb{R}^+$ means $v_i$ owes $d_{ij}$ to $v_j$. The edge set $E$ is the debt structure.

Two quantities describe each entity. The balance is everything owed to the entity minus everything it owes:

$$\mathrm{balance}(v_i) = \sum_{j=1,\,j\neq i}^{n} d_{ji} - \sum_{j=1,\,j\neq i}^{n} d_{ij}.$$

The transferable amount is the value that, when all debts are settled, moves straight through the entity from its debtors to its creditors:

$$\mathrm{transferable}(v_i) = \min\!\left( \sum_{j=1,\,j\neq i}^{n} d_{ji},\; \sum_{j=1,\,j\neq i}^{n} d_{ij} \right).$$

Simplifying the system means reducing this pass-through: every unit that merely flows through an intermediary is a transaction that did not need to happen.

Compensating Debt

Take the simplest instance: all debts are sums of currency, the denomination is (near) fractional, and every entity accepts a debt from any other party. Build the graph and compute each party’s balance. The balances always sum to zero, because every debt is counted once positively and once negatively:

$$\sum_{i=1}^{n} \mathrm{balance}(v_i) = \sum_{i=1}^{n}\!\left( \sum_{j} d_{ji} - \sum_{j} d_{ij} \right) = \sum_{i}\sum_{j} d_{ji} - \sum_{i}\sum_{j} d_{ij} = 0.$$

A party is a net debtor if its balance is below zero and a net creditor if above. Anyone with equal debt and credit has balance zero and drops out of the problem entirely.

This gives an immediate solution. Introduce a neutral party $v_{n+1}$. For every net debtor add an edge to $v_{n+1}$ with weight $|\mathrm{balance}(v_i)|$; for every net creditor add an edge from $v_{n+1}$ with weight $|\mathrm{balance}(v_i)|$. Remove all other edges. The neutral party collects from the debtors and redistributes to the creditors, and every original party now has exactly one transaction to make.

This is central clearing. A central counterparty novates every bilateral contract, and the whole graph collapses to a star. Much of the over-the-counter derivatives market was pushed onto this structure after 2008, under Dodd-Frank in the United States and EMIR in Europe.

A solution is optimal when no party has both debt and credit, which is to say when the graph has no path of length two or more. We can pose the corresponding decision problem: can the debts be reduced so that $|E| \le k$ for some chosen $k$?

Trust Relations

Credit and debt are forms of trust. A creditor may not want to swap a debt owed by a party it does business with for a debt owed by a party it knows nothing about, especially when the debt is a long-term loan, or the unknown party sits in an economically sensitive sector.

Call a debtor $v_i$ external to a creditor $v_j$ if there is no path from $v_i$ to $v_j$ in the original problem. Now consider the variant where entities refuse debt from parties external to them. The clearing-party trick no longer works: routing everything through a neutral hub can leave a creditor indirectly dependent on an external debtor once the hub redistributes.

We can still reduce the transferable amount without violating trust, by only ever short-circuiting debts that already share an endpoint. For each entity, repeatedly match one of its incoming debts against one of its outgoing debts and route that amount directly from the upstream debtor to the downstream creditor:

function ReduceDebts(G(V, E)):
    for each v in V:
        I ← in-edges of v
        O ← out-edges of v
        while I ≠ ∅ and O ≠ ∅:
            pick e(s, v) ∈ I with weight d_i
            pick e(v, t) ∈ O with weight d_o
            d ← min(d_i, d_o)
            if an edge e(s, t) with weight d_st exists:
                d_st ← d_st + d
            else:
                add edge e(s, t) with weight d
            if d_i = d:
                I ← I − {e(s, v)}
            else:
                O ← O − {e(v, t)}
    return G(V, E)

Because the new edge $e(s, t)$ only connects a party that already reached $v$ to one $v$ already reached, no new trust relation is created that the original graph did not permit.

Running time. The procedure is in NP, since a solution is verified in polynomial time by checking that the transferable amount of every party is zero, and it runs in $\mathrm{O}(|V|^2)$ time. The outer loop runs exactly $|V|$ times. A vertex has at most $|V| - 1$ incident edges, and each pass of the inner loop removes at least one of them, so the inner loop runs at most $|V| - 2$ times. After that either $I$ or $O$ is empty, the transferable amount is zero, and the party is optimal. The sets $I$ and $O$ only ever shrink, since no debt is created out of nothing, so the bound holds.

ReduceDebts is the decentralised cousin of clearing, known in practice as portfolio compression. There is no central counterparty, only bilateral tear-ups that preserve each party’s net position. The procedure is deliberately local, and its outcome is order-dependent: which debts you short-circuit, and in which order, changes the result, and there is no canonical optimum. Compression services such as TriOptima’s triReduce grew large after 2008 to shrink gross notional under leverage-ratio rules. D’Errico and Roukny (2017) model exactly this as a graph problem.

Fixed Transaction Costs

A different variant: all debts are accepted, but settling one incurs a fixed cost that is independent of the amount, a flat transaction fee. When debtors and creditors do not match one to one, minimising the total cost is no longer trivial, and the question becomes how to settle everyone in the fewest transfers.

This has a clean structural answer. Drop the parties whose balance is already zero. The minimum number of transfers is then $n - k$, where $k$ is the largest number of zero-sum groups the balances partition into. A group of $m$ parties settles internally in exactly $m - 1$ transfers, and independent groups do not interact, so minimising transactions means maximising the number of zero-sum groups. Merely deciding whether you can beat the trivial $n - 1$, which is to say whether any proper zero-sum subset exists at all, is already the Subset Sum problem, and so NP-complete.

With arbitrary debtor-to-creditor transfers and a flat charge per used edge, this is the fixed-charge transportation problem, a classic NP-hard problem in combinatorial optimisation. The greedy rule that expense-splitting apps use, largest debtor pays largest creditor, is a heuristic with no constant-factor guarantee.

Dependent Debt

The richest variant treats a debt as a semi-finished product or material in a production process. A party is now a producer or purchaser of some commodity, and its transferable amount is the total it must produce in order to pay off its own suppliers.

This invites a failure mode that currency debt does not have. A producer can come to depend, indirectly, on itself: a blocked production line. In the graph this is a directed cycle: $v_1$ needs an input from $v_2$, which needs one from $v_3$, which needs one back from $v_1$. Nothing can start. The deadlock cannot be cleared without some external party investing into the cycle.

The problem becomes: find a set of edges $E' \subset E$ that, when removed, makes the graph acyclic, while minimising the total cost of the removed edges. This is the Minimum Cost Feedback Arc Set, a weighted version of the Feedback Arc Set decision problem (does there exist $E' \subset E$ with $|E'| \le k$ whose removal makes $G$ acyclic?). The minimum-cost version is at least as hard as ordinary Feedback Arc Set; run the cost algorithm on a graph with all edge weights equal to one.

Feedback Arc Set is NP-complete

FAS is in NP. Given an instance $G(V, E)$ and a candidate solution $E'$, assert $|E'| \le k$, let $G' = (V, E - E')$, and build a spanning tree of $G'$ by depth-first search. If a back-edge is found the graph still has a cycle, so $E'$ is not a solution. The certificate is valid iff $G'$ is acyclic and $|E'| \le k$, which is checkable in polynomial time.

FAS is NP-hard, by reduction from Minimum Vertex Cover, itself a known NP-complete problem. A vertex cover is a set $V' \subseteq V$ such that every edge of $G$ touches at least one vertex in $V'$; the decision version asks whether one of size $\le K$ exists.

Given a Vertex Cover instance $G(V, E)$, construct a directed graph $G'(V', E')$:

• For each vertex $v_i \in V$, create two vertices $v_i$ and $v_i'$ joined by a directed edge $e(v_i, v_i')$.
• For each undirected edge $e(v_i, v_j) \in E$, add the two directed edges $e(v_j', v_i)$ and $e(v_i', v_j)$.

Every cycle in $G'$ must pass through some “internal” edge $e(v_i, v_i')$, and there is exactly one such edge per original vertex. Removing $e(v_i, v_i')$ corresponds to placing $v_i$ in the cover. A set of internal edges breaks all cycles in $G'$ if and only if the corresponding vertices cover all edges of $G$, so a minimum Feedback Arc Set in $G'$ yields a minimum Vertex Cover in $G$, and the two problems have the same hardness.

Takeaways

• Pure-currency netting with universal trust is easy: a single clearing party reduces the whole system to one transaction per participant, because balances sum to zero.
• Add trust constraints and you give up the clearing party, but an $\mathrm{O}(|V|^2)$ pass that only short-circuits already-connected debts still reduces the pass-through without inventing new exposures.
• The realistic frictions are where it gets hard. Flat transaction fees make the problem Subset Sum (NP-complete); production dependencies make it Minimum Cost Feedback Arc Set (NP-hard).

Each of the three problems in the dissertation followed this shape: write the financial system as a graph, and the question you actually care about turns out to be a named graph problem whose difficulty is already understood. The companion posts do the same for portfolio diversification and currency arbitrage.

References

• R. M. Karp (1972). Reducibility Among Combinatorial Problems. Vertex Cover, Feedback Arc Set, and Subset Sum (as Knapsack) are among the 21 problems shown NP-complete here.
• M. D’Errico and T. Roukny (2017). Compressing Over-the-Counter Markets. Models multilateral portfolio compression as a network problem.