The Propagation Depth of Local Consistency

Christoph Berkholz

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$-consistenc…