Skip to Main content Skip to Navigation
Conference papers

Revisiting Neighborhood Inverse Consistency on Binary CSPs

Robert J. Woodward 1 Shant Karakashian 1 Berthe Y. Choueiry 1 Christian Bessière 2
2 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Our goal is to investigate the definition and application of strong consistency properties on the dual graphs of binary Constraint Satisfaction Problems (CSPs). As a first step in that direction, we study the structure of the dual graph of binary CSPs, and show how it can be arranged in a triangle-shaped grid. We then study, in this context, Relational Neighborhood Inverse Consistency (RNIC), which is a con- sistency property that we had introduced for non-binary CSPs. We discuss how the structure of the dual graph of binary CSPs affects the consistency level enforced by RNIC. Then, we compare, both theoreti- cally and empirically, RNIC to Neighborhood Inverse Consistency (NIC) and strong Conservative Dual Consistency (sCDC), which are higher- level consistency properties useful for solving difficult problem instances. We show that all three properties are pairwise incomparable.
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Joël Quinqueton Connect in order to contact the contributor
Submitted on : Monday, November 5, 2012 - 9:31:56 AM
Last modification on : Monday, October 11, 2021 - 1:24:07 PM
Long-term archiving on: : Wednesday, February 6, 2013 - 3:53:50 AM


Files produced by the author(s)


  • HAL Id : lirmm-00748179, version 1



Robert J. Woodward, Shant Karakashian, Berthe Y. Choueiry, Christian Bessière. Revisiting Neighborhood Inverse Consistency on Binary CSPs. CP: Principles and Practice of Constraint Programming, Oct 2012, Québec City, Canada. pp.688-703. ⟨lirmm-00748179⟩



Record views


Files downloads