The Assignment Problem is a polynomial problem, restated graphically
as optimal weighted dimer covering on a bipartite graph. The Hungarian
Algorithm (Kuhn, 1955) is a performing solution tool, which involves
the construction of graphical structures. We show how the RS Cavity
Method (a.k.a. Belief Propagation) allows to devise a new exact
algorithm, which is elementary, purely algebraic and interruptible.

This construction is intended also as a playground to understand
aspects of the more subtle 1RSB Cavity Method (a.k.a. Survey
Propagation) in hard problems, and its approximations due to feedback
loops. Indeed, a crucial lemma in proving that Cavity solves the
Assignment Problem (Bayati-Shah-Sharma, 2005) relies on the
comprehension of the virtuous role of loops within the algorithm.