Abstract: The debts' clearing problem is about clearing all the debts in a group of $n$ entities (eg. persons, companies) using a minimal number of money transaction operations. In a previous paper we conjectured the problem to be NP-complete. In this paper we prove that it is NP-hard in the strong sense and also NP-easy. We also show the same results for a restricted version of the problem.
Keywords: debt clearing, NP-hard, NP-easy, minimum edge-cost flow
Classification (MSC2000): 68Q17; 05C21
Full text of the article: