On the existential 2-pebble game and arc consistency algorithms

Christoph Berkholz

We investigate the connection between arc consistency algorithms and the existential 2-pebble game. It is known that Spoiler has a winning strategy in the existential 2-pebble game on two vertex-colored graphs G and H iff the arc consistency test rejects the instance (i.e. reports that there is no homomorphism from G to H). A lot of sequential and parallel arc consistency algorithms have been proposed in the literature and all essentially rely on a simple propagation rule. We show how the complexity of such propagation based (sequential/parallel) arc consistency algorithms is related to the number-of-rounds Spoiler needs to win the existential 2-pebble game. Furthermore, we obtain lower bounds on the number of propagation-steps in arc consistency algorithms via proving lower bounds on the number-of-rounds in the existential 2-pebble game.

This is joint work with Oleg Verbitsky.