AAAI Publications, Tenth Symposium of Abstraction, Reformulation, and Approximation

Font Size: 
Incorrect Lower Bounds for Path Consistency and More
T. K. Satish Kumar, Liron Cohen, Sven Koenig

Last modified: 2013-06-19


In this paper, we present an efficient algorithm for verifying path-consistency on a binary constraint network. The complexities of our algorithm beat the previous conjectures on the lower bounds for verifying path-consistency. We therefore defeat the proofs for several published results that incorrectly rely on these conjectures. Our algorithm is motivated by the idea of reformulating path-consistency verification as fast matrix multiplication. Further, for a computational model that counts arithmetic operations (rather than bit operations), a clever use of the properties of prime numbers allows us to design an even faster variant of the algorithm. Based on our algorithm, we hope to inspire a new class of techniques for verifying and even establishing varying levels of local-consistency on given constraint networks.


Constraint Satisfaction, Algorithms and Complexity

Full Text: PDF