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

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.