Susceptibility Propagation for Constraint Satisfaction Problems

Saburo Higuchi 1, Marc Mézard 2

Journal of Physics 233, 1 (2010) 012003

We study the susceptibility propagation, a message-passing algorithm to compute correlation functions. It is applied to constraint satisfaction problems and its accuracy is examined. As a heuristic method to find a satisfying assignment, we propose susceptibility-guided decimation where correlations among the variables play an important role. We apply this novel decimation to locked occupation problems, a class of hard constraint satisfaction problems exhibited recently. It is shown that the present method performs better than the standard belief-guided decimation.

  • 1. Department of Applied Mathematics and Informatics,
    Ryukoku Univsersity
  • 2. Laboratoire de Physique Théorique et Modèles Statistiques (LPTMS),
    CNRS : UMR8626 – Université Paris XI - Paris Sud