The Propagation Depth of Local Consistency

We establish optimal bounds on the number of nested propagation steps in k -consistency tests. It is known that local consistency algorithms such as arc-, path- and k -consistency are not efficiently parallelizable. Their inherent sequential nature is caused by long chains of nested propagation steps, which cannot be executed in parallel. This motivates the question What is the minimum number of nested propagation steps that have to be performed by k -consistency algorithms on (binary) constraint networks with n variables and domain size d? The number of nested propagation steps equals the minimum number of rounds Spoiler needs to win the existential k -pebble game on two structures with universes of size n and d. By applying involved tools from finite model theory we show that the trivial upper bound of n k -1 d k -1 is tight. As a consequence we get optimal lower bounds on the quantifier rank of existential-positive k -variable first-order sentences and on the propagation depth of k -consistency tests.

Authors

• Christoph Berkholz

Keywords

No keywords are indexed for this paper.