# A note on the NP-completeness of the integral netting problem

Nazim Fatès

► To cite this version:

Nazim Fatès. A note on the NP-completeness of the integral netting problem. Inria Nancy - Grand Est. 2026. hal-05528103

HAL Id: hal-05528103

https://inria.hal.science/hal-05528103v1

Submitted on 26 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# A note on the NP-completeness of the integral netting problem

Nazim Fatès

February 26, 2026

## Abstract

We consider a situation where various actors simultaneously owe some debt to each other. Modelling a network of debts with a multi-graph, we examine the complexity of the *netting problem*, that is, finding the maximum amount of debt cleared with a fixed monetary supply that finances the negative net positions after the debt have been cancelled.

We show that the netting problem is NP-complete in its integral version, that is, when each arc is either kept in the graph or completely removed. Although this result is already known (Güntzer et al. [1]), we believe that a direct reduction to SAT has its own interest. We thus present a construction that transforms a CNF formula into a multi-graph whose maximum clearing debt determines the satisfiability of the formula.

## 1 Definitions

The phenomenon of debt is observed in all kind of societies and in modern economies, it is a crucial mechanism for a healthy functioning. In various kinds of markets, at a given time many interlocked debts may exist (banks, companies, etc.). This network of mutual obligations can be modelled by a multigraph where the vertices are the economic actors, e.g., companies, and where the arcs represent a debt from the source to the destination. If a given subset of arcs is removed from the graph, a certain quantity of debt will also be removed, the *settlement*, but, in general, differences will remain in the net positions of the actors. The netting problem consists in finding the maximal settlement given a fixed external amount, the *financing*, which is used to compensate the resulting negative net positions.

Informally, the *integral netting problem* (INP), or *integral netting* for short, consists, given a graph, in finding a subset of arcs that achieves the best compromise between:

a) maximising the amount of debt cleared, and,

b) minimising the supply of liquidity required to clear it.

The term *mutual debt compensation* (or mutual debt reduction) has also been used to qualify this mechanism of debt clearing (see e.g. Ref. [2, 3]). Here,
we prefer to use the term *netting* as it is shorter. The adjective *integral* relates to the fact that the invoices are *fully financed*, that is, an invoice is either fully removed or kept untouched (the debts cannot be diminished).

Let us now make the definition of **integral netting** more formal. We follow the lines of our previous work [3].

Let $G = (V, A)$ be an oriented weighted multi-graph. The set of vertices $V$ is arbitrary and we set $A = V \times V \times \mathbb{N}$, that is, the arcs are triplets where the first, second and third elements are respectively the *source* $s(a)$, the *destination* $d(a)$, and the *weight* $\varphi(a)$ of the arc $a$. We call a *configuration* the set of invoices that is selected to be financed. Formally, this corresponds simply to a subset of arcs; it should be the output of the algorithm that solves **integral netting** with the input $G = (V, A)$.

For a configuration $C \subset A$, we define the *settlement* of $C$ as the total weight included in this configuration: $\Sigma(C) = \sum_{a \in C} \varphi(a)$. This corresponds to the total value of the debt that is cleared in $C$.

For $G = (V, A)$ and given a vertex $v \in V$, we denote by $I(v)$ (resp. $O(v)$) the incoming (resp. outgoing) arcs of $v$, that is, the arcs which have $v$ as a destination (resp. as a source): $I(v) = \{a \in A, d(a) = v\}$ and $O(v) = \{a \in A, s(a) = v\}$. Given a configuration $C$, the *net position over C of a vertex* $v \in V$, denoted by $\pi_C(v)$, is the difference between the incoming and outgoing total weight. Formally:

$$ \pi_C(v) = \sum_{a \in I(v) \cap C} \varphi(a) - \sum_{a \in O(v) \cap C} \varphi(a). $$

This represents the balance of $v$ after the invoices of $C$ have been settled. Note that, by definition, the vertices which are not involved in $C$ have a zero net position over $C$.

Given a configuration $C$, the *financing* of $C$, denoted by $\Phi(C)$ is the sum of the negative net positions over $C$:

$$ \Phi(C) = \sum_{v: \pi_C(v) < 0} -\pi_C(v). $$

$\Phi(C)$ corresponds to the amount that needs to be provided by an external counterparty to clear the debt contained in $C$. The mutual debts between the different actors are then transformed in a debt towards this external counterparty.

Our problem consists in settling as much debt as possible given a maximal financing value. We thus define **integral netting** as:

Given a maximal financing value $\Phi^*$, find a configuration $C^*$ which maximises the settlement $\Sigma(C^*)$ in the set of configurations that require a financing less than or equal to $\Phi^*$:

$$ C^* = \underset{C:\Phi(C) \le \Phi^*}{\operatorname{argmax}} \{\Sigma(C)\}. $$
<figure><img src="image_2.png" /><figcaption>Figure 1: Decision modules for the variables $x$, $y$ and $z$. In $\mathcal{F}$, $x$ appears three times, $\neg y$ appears twice, and $\neg z$ and $z$ appear once (special case).</figcaption></figure>

# 2 Construction

We present graph how to associate to a general formula $F$ a graph $G_F$ constructed in such a way the existence of a solution to integral netting is equivalent to the existence of a solution to the SAT problem for $F$. However, before presenting the general case, let us examine a small example.

## 2.1 Example formula

Let us take as an example the three-variable four-clause formula:

$$ \mathcal{F} = x \wedge (\neg x \vee y \vee z) \wedge (\neg x \vee y) \wedge (\neg x \vee \neg z). $$

Note that we use here $x, y, z$ instead of $x_1, x_2, x_3$ for the sake of readability. Also note that the formula is obviously satisfiable, and that it has a unique solution $(x, y, z) = (\text{True}, \text{True}, \text{False})$.

We want to construct a graph $G_F$ such that any solution to integral netting will also encode the solution to the SAT problem for $\mathcal{F}$. We focus on the special case of zero-financing: we will look at the optimal settlement obtained with configuration $C^*$ such that $\phi(C^*) = 0$.

The first elements that we insert in $G_F$ are the three decisions modules that appear in Figure 1. The role of these modules is to force a decision True or False for each variable. Since $x$ appears three times in negated form and once in a non-negated form, we take the maximum of 3 and 1 and say that the multiplicity of $x$ is equal to 3. We construct the decision module of this variable with an arc of weight 3 from $x_i^d$ (down) to $x_i^u$ (up), and the two arcs of weight 3 from $x_i^u$ to $x_i^-$ and $x_i^+$, respectively. Finally, we put three arcs of weight 1 from $x_i^-$ to $x_i^d$, and from and $x_i^+$ to $x_i^d$.

We proceed in the same way for $y$, as it has a multiplicity of 2, but the case of $z$ is special since its multiplicity is 1. Here, we still need to put a weight of 2 in order to force a choice between $z^-$ and $z^+$, but we keep only one arc between each node of the module.

We then add to $G_F$ four clause modules with the vertices $\alpha_1, \dots, \alpha_4$ and $\beta_1, \dots, \beta_4$, connected to the other vertices as presented on Figure 2. The role of these module is quite simple: they should allow the formation of a circuit if and only if their clause is satisfiable with the assignment that was made in the decision modules.
In our case, the first clause is atomic ($x$): the vertex $\alpha_1$ connects $x^-$, $x^d$ connects $\beta_1$ and $\beta_1$ connects $\alpha_1$. We can thus form of circuit with four arcs of weight 1 by adding an arc from $x^-$ to $x^d$, and this arc is free because the decision module used the arcs from $x^+$ to $x^d$ to close the circuits. Similarly, for the second clause ($\neg x \lor y \lor z$), $\alpha_2$ respectively connects $x^+$, $y^-$ and $z^-$. These three arcs correspond to the possible choices to make this clause true, that is, by closing a circuit. The same applies for the third and the four clause.

Without entering too much into the details, readers can verify that the configuration $C^*$ presented on Figure 3 is optimal for the special case $\phi = 0$, that is, for the zero-financing case ($\Phi(C) = 0$). It has a settlement of 37 units, as the three circuits in the decision modules clear $3 \times 3 + 3 \times 2 + 3 \times 2 = 21$ units and the four circuits in the clause circuits clear $4 \times 4 = 16$ units.

## 2.2 Description of the graph associated to a SAT formula

We now explain how to transform into a graph a general formula $F$, which is assumed to be written in conjunctive normal form, with $n$ variables ($x_1, \dots, x_n$), and $k$ clauses ($C_1, \dots, C_k$). Without loss of generality, we assume that each variable appears at least once in $F$ and that there is no clause which contains the same variable twice. The associated graph $G_F$ will be formed of the following vertices: $x_i^u$, $x_i^d$, $x_i^+$, and $x_i^-$, for $i \in \{1, \dots, n\}$, and $\alpha_j$, $\beta_j$, for $j \in \{1, \dots, k\}$.

The main idea associated to the reduction is to use the special case of zero-financing, which implies that the configuration of a maximum weight will be a union of circuits. The graph $G_F$ associated to a binary formula $F$ is built with arcs that belong to two types of modules: as seen above, the decision modules encode the value of the boolean variables $x_i$, while the clause modules encode the fact that each clause is satisfied when $F$ is satisfiable. We now describe these elements in detail.

## 2.3 Decision modules

To each variable $x_i$, we associate a decision module $M_i$, formed of the four vertices $x_i^u$, $x_i^d$, $x_i^+$ and $x_i^-$.

Recall that the role of this module is to force a decision **True** or **False** for each variable. We encode $x_i = \text{True}$ by closing a circuit, called the *decision cycle*, which joins $x_i^d$, $x_i^u$, and $x_i^+$, leaving $x_i^-$ free. Symmetrically, for encoding $x_i = \text{False}$, we close the circuit between $x_i^d$, $x_i^u$, and $x_i^-$ and leave $x_i^+$ free.

Assuming that the variable $x_i$ appears $n_i$ times and $p_i$ times in a negated and non negated-form in $F$, respectively, we define the *multiplicity* $m_i$ as: $m_i = \max\{n_i, p_i\}$. This quantity is used to set the number of arcs between $x_i^-$ and $x_i^d$, and, similarly, between $x_i^+$ and $x_i^d$.

Our goal is to ensure that each decision module will form a cycle of weight at least 6. This quantity is arbitrarily chosen and can be made as high as one wishes. The only constraint is that the weight of the circuit in the decision module should be greater than the weight of the circuit in the clause modules.
We thus define each decision module $M_i$ according to the value of the multiplicity. For the case $m_i \ge 2$, we have:

$$M_i = \{(x_i^d, x_i^u, m_i), (x_i^u, x_i^+, m_i), (x_i^+, x_i^d, 1)^{m_i}, (x_i^u, x_i^-, m_i), (x_i^-, x_i^d, 1)^{m_i}\}.$$

The case of a multiplicity of 1 is a special case; for $m_i = 1$, we set:

$$M_i = \{(x_i^d, x_i^u, 2), (x_i^u, x_i^+, 2), (x_i^+, x_i^d, 2), (x_i^u, x_i^-, 2), (x_i^-, x_i^d, 2)\}.$$

This guarantees that the weight of the cycle in the decision module is at least 6, which “forces” a decision True or False for each variable to obtain a configuration of maximal weight. Figure 1 illustrates the decision modules associated to $x$, $y$, and $z$ (particular case) for the example of formula $\mathcal{F}$.

In the rest of the text, we will use the adjusted multiplicity $\tilde{m}_i$ defined as $\tilde{m}_i = \max\{2, m_i\}$ to avoid the disjunction of cases between $m_i = 1$ and $m_i > 1$.

## 2.4 Clause modules

For each clause $C_i$, we use two vertices, $\alpha_i$ and $\beta_i$. Assume that $C_i$ is formed with $n_i$ variables, whose indices are $v_i^1, \dots, v_i^{n_i}$. Let $D_j^i = x_j^d$ denote the “output vertex” of the $v_i^j$-th decision module. Moreover, let $S_j^i$ denote $x_j^+$ if the variable of index $v_i^j$ is negated and denote $x_j^-$ otherwise. This corresponds to the vertex that is potentially left free by the decision module (see above). For example, for $C_i = x_2 \lor \neg x_3 \lor \neg x_7$, we would have $D_1^i = x_2^d$, $D_2^i = x_3^d$ and $D_3^i = x_7^d$, and, $S_1^i = x_2^-, S_2^i = x_3^+$, and $S_3^i = x_7^+$.

We then define the clause module $C_i$ as: $C_i = \bigcup_{j=1}^{n_i} \kappa(i, j)$, with

$$\kappa(i, j) = \{(\alpha_i, S_j^i, 1), (D_j^i, \beta_i, 1), (\beta_i, \alpha_i, 1)\}.$$

When a given clause $C_i$ is satisfiable with a particular assignment of the variables, the corresponding clause module can hold a circuit of weight 4 by adding an arc $(S_j^i, D_i^j, 1)$ to $\kappa(i, j)$ for given $j$. Examples of such circuits are presented in Fig. 3.

## 2.5 Properties

Recall that $F$ has $k$ variables and that $\tilde{m}_i$ is the “adjusted multiplicity” of each variable $x_i$ (see Sec. 2.3).

**Proposition 1.** $F$ is satisfiable if and only if its associated graph $G_F$ contains a zero-financing configuration $C^*$ whose settlement equals $\Sigma(C^*) = 4k + 3 \sum_{i=1}^n \tilde{m}_i$.

*Proof.* $\implies$ Assume that $F$ is satisfiable with the assignment $(x_i)_{i \in \{1, \dots, n\}}$. Then, for each clause $C_i$, there is a signed variable $X_i$ which satisfies $C_i$. For example, for $\mathcal{F}$, for the assignment $(x, y, z) = (\text{True}, \text{True}, \text{False})$, we can take $T_1 = x, T_2 = T_3 = y, T_4 = \neg z$. Note that the choice $T_3 = \neg z$ is also possible.
<figure><img src="image_3.png" /><figcaption>Figure 2: Graph $G_F$ that encodes the formula $\mathcal{F}$.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Figure 3: Reduction: a zero-financing configuration of $G_F$ that encodes the instance $(x, y, z) = (\text{True}, \text{True}, \text{False})$, which satisfies $\mathcal{F}$.</figcaption></figure>
Let $c_i$ and $d_i$ be such that $(c_i, d_i) = (\bar{x}_i, x_i^+)$ if $T_i$ corresponds to a negated variable and such that $(c_i, d_i) = (x_i^+, \bar{x}_i)$ otherwise. Remark that $c_i$ and $d_i$ will respectively be used in circuits which belong to a **clause** and **decision** module.

First, for each variable $x_i$, we include in the configuration $C^*$ the *decision circuits*, which contain all the arcs between $x_i^u$, $x_i^d$ and $d_i$. By construction, these arcs form a circuit of weight $3 \sum \tilde{m}_i$ (see Fig. 3).

For each clause module, we add to $C^*$ the four-arc *clause circuits*, which link the following vertices: $\alpha_i$, $c_i$, $x_i^d$, and $\beta_i$. By construction, each such circuit can indeed be found in $G_F$ (see Sec. 2.3) and has a weight of 4. The configuration $C$ thus has a weight $\Sigma(C) = 4k + 3 \sum_{i=1}^n \tilde{m}_i$, and, since it is composed of a union of circuits, its financing is zero.

Let us assume that $G_F$ contains a zero-financing configuration $C^*$ with a weight equal to $\Sigma = 4k + 3 \sum_{i=1}^n \tilde{m}_i$. First, one can verify that $C^*$ necessarily includes the decision circuits and the clause circuits described above. By following which vertices are implied in the clause circuits, one finds an assignment that satisfies $F$.

Second, we claim that any other configuration of $G_F$ that is a union of circuits has a weight less or equal than $\Sigma$. Indeed, by construction, we can list all the possible circuits and divide them into two groups: those which include $\alpha_i$ and $\beta_i$, the clause circuits, and those which include $x_i^u$, the decision circuits. On the one hand, since there is only one link from $\beta_i$ to $\alpha_i$, the best one can do is to close such circuits with a weight of 4. Indeed, informally, one can observe that, apart from the arcs from $\beta_i$ to $\alpha_i$, all the arcs have a downward direction. On the other hand, for each variable $x_i$, the decision circuits can only be closed by including an arc from $x_i^d$ to $x_i^u$, which then forces a choice between $\bar{x}_i$ and $x_i^+$ to close the circuits, by adding $\tilde{m}_i$ unitary arcs from the vertex chosen to $x_i^d$.

In other words, by adding all these circuits, we necessarily recover a configuration with a weight equal to $\Sigma = 4k + 3 \sum_{i=1}^n \tilde{m}_i$. In the case where the formula is not satisfiable, e.g., for $F' = x \wedge (\neg x \vee \neg y \vee z) \wedge (\neg x \vee y) \wedge (\neg x \vee \neg z)$, a conflict will occur for at least one clause between the decision circuits and the clause circuits, leading to a settlement of strictly smaller value. $\square$

**Integral netting** is thus NP-hard: having a polynomial-time solution to this problem implies having a polynomial-time solution to the SAT problem. It is also clearly in NP, since a configuration can be chosen by a non-deterministic Turing machine and it can be verified in polynomial by such a machine if it is indeed a zero-financing configuration and there is no other zero-financing configuration with a higher settlement.

## Acknowledgments

The author is grateful to Sylvain Contassot-Vivier and Joannès Guichon for their encouragement and for their valuable comments, which greatly improved the presentation of this note.
References

[1] Michael M. Güntzer, Dieter Jungnickel, and Matthias Leclerc. “Efficient algorithms for the clearing of interbank payments”. In: *European Journal of Operational Research* 106.1 (1998), pp. 212–219. DOI: 10.1016/S0377-2217(97)00265-8.

[2] Gazda Vladimír, Denis Horváth, and Marcel Rešovský. “An application of graph theory in the process of mutual debt compensation”. In: *Acta Polytechnica Hungarica* 12.3 (2015), pp. 7–24.

[3] Massimo Amato, Nazim Fatès, and Lucio Gobbi. *The economics and algorithmics of an integral settlement procedure on B2B network*. Research report SSRN. 2021. DOI: 10.2139/ssrn.3915380.