Constraint Propagation and Pebble Games

From International Center for Computational Logic

Constraint Propagation and Pebble Games

Talk by Christoph Berkholz
  • Location: WIL C115
  • Start: June 3, 2016 at 1:15 pm
  • End: June 3, 2016 at 2:15 pm
  • iCal
A generic method for solving the constraint satisfaction problem is "constraint propagation" where one iteratively derives new constraints in order to shrink the search space or to detect inconsistencies in the instance. A classical and very basic algorithm in this area is the so-called k-consistency test that iteratively derives local constraints involving only k variables. In this talk I will give an introduction to this method and show that the k-consistency test is tightly connected to a simple combinatorial pebble game originally introduced in the context of finite model theory. Afterwards I will present some results on the structure and complexity of the k-consistency test that have been obtained via this pebble game in the last years.