**
Acta Mathematica Academiae Paedagogicae Nyíregyháziensis, Vol. 28, No. 2, pp. 217-226 (2012)
**

#
The debts' clearing problem's relation with complexity classes

##
Csaba Patcas

Babes-Bolyai University

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

[Previous Article] [Contents of this Number]

*
© 2013
FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition
*