On the speed of constraint propagation and the time complexity of arc consistency testing

•The time complexity of arc consistency is estimated for any propagation-based algorithm.•The obtained lower and upper bounds are tight up to a constant factor.•Examples of slow constraint propagation are analyzed by methods of finite model theory.

Establishing arc consistency on two relational structures is one of the most popular heuristics for the constraint satisfaction problem. We aim at determining the time complexity of arc consistency testing. The input structures G and H can be supposed to be connected colored graphs, as the general problem reduces to this particular case. We first observe the upper bound O(e(G)v(H)+v(G)e(H)), which implies the bound O(e(G)e(H)) in terms of the number of edges and the bound O((v(G)+v(H))3) in terms of the number of vertices. We then show that both bounds are tight as long as an arc consistency algorithm is based on constraint propagation (as all current algorithms are). Our lower bounds are based on examples of slow constraint propagation. We measure the speed of constraint propagation observed on a pair G,H by the size of a combinatorial proof that Spoiler wins the existential 2-pebble game on G,H.