中科院数学与系统科学研究院

数学研究所

学术报告会

报告人：Prof. Sanjiang Li (University of Technology Sydney)

题  目：Exploring Directional Path-Consistency for Solving Binary Constraint Networks

时  间：2017.05.02（星期二），10:00-11:00

地  点：数学院南楼N818室

Abstract: Among the local consistency techniques used for solving constraint networks, path-consistency (PC) has received a great deal of attention. However, enforcing PC is computationally heavy and sometimes even unnecessary. Directional path-consistency (DPC) is a weaker notion of PC that considers a given variable ordering and can thus be enforced more efficiently than PC. This paper aims to characterize the binary constraint languages G such that DPC (the DPC enforcing algorithm of Dechter and Pearl) decides the constraint satisfaction problem (CSP) of G. We prove that these constraint languages, if they are complete in the sense that all of their definable relations are within them, are exactly those that have the Helly property. We also present a simple variant of the DPC algorithm, called DPC+, which can decide the CSPs of more general binary constraint languages. We show that the CSP of a binary constraint language can be decided by DPC+ if it is majority-closed. In fact, DPC+ is sufficient for guaranteeing backtrack-free search for such constraint networks.