Journal of Computer and System Sciences 91 (2018) 104114

Contents lists available at ScienceDirect

Journal of Computer and System Sciences

www.elsevier.com/locate/jcss

On the speed of constraint propagation and the time

complexity of arc consistency testing
Christoph Berkholz a , Oleg Verbitsky b,,1
a
RWTH Aachen University, Institut fr Informatik, D-52056 Aachen, Germany
b
Humboldt-Universitt zu Berlin, Institut fr Informatik, Unter den Linden 6, D-10099 Berlin, Germany

a r t i c l e i n f o a b s t r a c t

Article history: Establishing arc consistency on two relational structures is one of the most popular
Received 12 June 2014 heuristics for the constraint satisfaction problem. We aim at determining the time
Received in revised form 27 August 2017 complexity of arc consistency testing. The input structures G and H can be supposed
Accepted 7 September 2017
to be connected colored graphs, as the general problem reduces to this particular case.
Available online 19 September 2017
We rst observe the upper bound O (e (G ) v ( H ) + v (G )e ( H )), which implies the bound
Keywords: O (e (G )e ( H )) in terms of the number of edges and the bound O (( v (G ) + v ( H ))3 ) in terms
Constraint satisfaction problem of the number of vertices. We then show that both bounds are tight as long as an arc
Constraint propagation consistency algorithm is based on constraint propagation (as all current algorithms are).
Arc consistency Our lower bounds are based on examples of slow constraint propagation. We measure the
Time complexity speed of constraint propagation observed on a pair G , H by the size of a combinatorial
Existential 2-pebble game proof that Spoiler wins the existential 2-pebble game on G , H.
Existential-positive two-variable logic
2017 Elsevier Inc. All rights reserved.

1. Introduction

According to the framework of [1], the constraint satisfaction problem (CSP) takes two nite relational structures as input
and asks whether there is a homomorphism between these structures. In this paper we consider structures with unary and
binary relations and refer to unary relations as colors and to binary relations as directed edges. Note that this restricted
class of binary CSPs is known to be polynomial time equivalent to general CSPs [1]. In fact, most of the time we deal with
structures where the only binary relation E is symmetric and irreexive relation, i.e., with vertex-colored graphs. This is
justied by a linear time reduction from the CSP on binary structures to its restriction on colored graph; see Section 5.1.
Let G and H be an input of the CSP. It is customary to call the vertices of G variables and the vertices of H values.
A mapping from V (G ) to V ( H ) then corresponds to an assignment of values to the variables, and the assignment is satisfying
if the mapping denes a homomorphism. Let a domain D x V ( H ) of a variable x V (G ) be a set of values such that for
every homomorphism h : G H it holds that h(x) D x . The aim of the arc consistency heuristic is to nd small domains
in order to shrink the search space. The rst step of the arc consistency approach is to ensure node consistency, that is, D x
is initialized to the set of vertices in H that are colored with the same color as x. The second step is to iteratively shrink
the domains according to the following rule:

* Corresponding author.
E-mail address: verbitsk@informatik.hu-berlin.de (O. Verbitsky).
1
Supported by DFG grant VE 652/1-1. On leave from the Institute for Applied Problems of Mechanics and Mathematics, Lviv, Ukraine.

http://dx.doi.org/10.1016/j.jcss.2017.09.003
0022-0000/ 2017 Elsevier Inc. All rights reserved.
 C. Berkholz, O. Verbitsky / Journal of Computer and System Sciences 91 (2018) 104114 105

If there exists an a D x and a variable y V (G ) such that {x, y } E (G ) and {a, b}

/ E ( H ) for all b D y , then delete a
from D x .

A pair of graphs augmented with a set of domains is arc consistent if the above rule cannot be applied and all domains
are nonempty. We say that arc consistency can be established for G and H , if there exists a set of domains such that G and H
augmented with these domains is arc consistent. Our aim is to estimate the complexity of the following decision problem.

AC-Problem
Input: Two colored graphs G and H.
Question: Can arc consistency be established on G and H?

Using known techniques, we observe that the AC-Problem can be solved in time O ( v (G )e ( H ) + e (G ) v ( H )), where v (G )
and e (G ) denote the number of vertices and the number of edges respectively. This gives us only a quadratic upper bound in
the overall input size (where the graphs are encoded using adjacency lists), so there could be a chance for improvement: Is it
possible to solve the AC-Problem in sub-quadratic or even linear time? In fact, we cannot rule out this possibility completely.
The rst author [2] recently obtained lower bounds for higher levels of k-consistency (note that arc consistency is equivalent
to 2-consistency). In particular, 15-consistency cannot be established in linear time and establishing 27-consistency requires
more than quadratic time on multi-tape Turing machines. The lower bounds are obtained in [2] via the deterministic time
hierarchy theorem and, unfortunately, these methods are not applicable to arc consistency because of the blow-up in the
reduction.
However, we show lower bounds for every algorithm that is based on constraint propagation. A propagation-based arc
consistency algorithm is an algorithm that solves the AC-Problem by iteratively shrinking the domains via the arc consistency
rule above. Note that all currently known arc consistency algorithms (e.g. AC-1, AC-3 [3]; AC-3.1/AC-2001 [4]; AC-3.2, AC-3.3;
AC-3d [5]; AC-4 [6]; AC-5 [7]; AC-6 [8]; AC-7 [9]; AC-8 [10], AC- [11]) are propagation-based in this sense. Different AC
algorithms differ in the principle of ordering propagation steps; for a general overview we refer the reader to [4]. The upper
bound O ( v (G )e ( H ) + e (G ) v ( H )) implies O (e (G )e ( H )) in terms of the number of edges and O (n3 ) in terms of the number
of vertices n = v (G ) + v ( H ). Our main result, Theorem 5.3 in Section 5, states that both bounds are tight up to a constant
factor for any propagation-based algorithm.
We obtain the lower bounds by exploring a connection between the existential 2-pebble game and propagation-based
arc consistency algorithms. In its general form, the existential k-pebble game is an EhrenfeuchtFrass like game that
determines whether two nite structures can be distinguished in the existential-positive k-variable fragment of rst order
logic. It has found applications also outside nite model theory: to study the complexity and expressive power of Datalog
[12], k-consistency tests [1315,2] and bounded-width resolution [16,17]. It turns out that the existential 2-pebble game
exactly characterizes the power of arc consistency [13], i.e., Spoiler wins the existential 2-pebble game on two colored
graphs G and H iff arc consistency cannot be established.
The connection between the existential 2-pebble game and arc consistency algorithms is deeper than just a reformulation
of the AC-Problem. We show that every constraint propagation-based arc consistency algorithm computes in passing a proof
of Spoilers win on instances where arc consistency cannot be established. On the one hand these proofs of Spoilers win
naturally correspond to a winning strategy for Spoiler in the game. On the other hand they reect the propagation steps
performed by an algorithm. We consider three parameters to estimate the complexity of such proofs: length, size and depth.
The length corresponds to the number of propagation steps, whereas size also takes the cost of propagation into account.
The depth corresponds to the number of nested propagation steps and precisely matches the number of rounds D (G , H )
Spoiler needs to win the game. We observe that the minimum size of a proof of Spoilers win on G and H bounds from
below the running time of sequential propagation-based algorithms, whereas the minimal depth matches the running time
of parallel algorithms.
We exhibit pairs of colored graphs G , H where D (G , H ) = ( v (G ) v ( H )) and hence many nested propagation steps
are required to detect arc inconsistency. Because these graphs have a linear number of edges this implies that there is
no sub-quadratic propagation-based arc consistency algorithm. It should be noted that CSP instances that are hard for
sequential and parallel arc consistency algorithms, in the sense that they require many propagation steps, were explored
very early in the AI-community [18,19]. Such examples were also proposed to serve as benchmark instances to compare
different arc consistency algorithms [20]. Graphs G and H with large D (G , H ) can be derived from the old Domino example
[20], consisting of structures with two binary relations. We also provide a new example, which we call Co-Wheels, that
shows the same phenomenon of slow constraint propagation for a more restricted class of rooted loopless digraphs.
The rest of the paper is organized as follows. In Section 2 we give the necessary information on the existential 2-pebble
game and use it to analyze the Domino pattern. Our Co-Wheels pattern is introduced and analyzed in Section 3. Section 4
is devoted to the winner proof system for the existential 2-pebble game. The facts obtained here are used in Section 5 to
prove our main results on the complexity of propagation-based algorithms for the AC-Problem.
A preliminary version of this paper appeared in [21].
106 C. Berkholz, O. Verbitsky / Journal of Computer and System Sciences 91 (2018) 104114

2. Preliminaries

A binary structure A is a relational structure over vocabulary = { E 1 , E 2 , . . . , U 1 , U 2 , . . .} consisting of binary relations

E i , i 1, and unary relations U j , j 1. Each binary relation E iA between elements of A can be regarded as a directed graph
with arrows (x, y ) E iA colored in color i. Similarly, the unary relations U Aj can be thought of as colors of elements of A.
In this way, we can consider A an edge- and vertex-colored directed graph. The elements of A will be then called vertices.
The set of the elements of A will be denoted by V ( A ) and their number by v ( A ).
In colored graphs we additionally have unary relations of vertex colors, i.e., = ( E 1 , U 1 , U 2 , . . .). Moreover, it is supposed
that any two color classes U Aj and U Aj are disjoint. The number of edges in a colored graph A is denoted by e ( A ).
The existential 2-pebble game on binary structures A and B [12] is played by two players, Spoiler and Duplicator, to whom
we will refer as he and she respectively. Each player has a pair of distinct pebbles p and q. A round consists of a move of
Spoiler followed by a move of Duplicator. Spoiler takes a pebble, p or q, and puts it on a vertex in A. Then Duplicator has
to put her copy of this pebble on a vertex of B. Duplicators objective is to keep the following condition true after each
round: the pebbling should determine a partial homomorphism from A to B.
Let x V ( A ) and u V ( B ) denote the vertices pebbled by p and y V ( A ) and v V ( B ) denote the vertices pebbled
by q. Thus, Duplicator loses as soon as x U Aj while u / U Bj for some j, or (x, y ) E iA while (u , v ) / E iB , or ( y , x) E iA
while ( v , u )
/ E iB for some i, or x = y while u = v.
For each positive integer r, the r-round existential 2-pebble game on A and B is a two-person game of perfect infor-
mation with a nite number of positions. Therefore, either Spoiler or Duplicator has a winning strategy in this game, that
is, a strategy winning against every strategy of the opponent. Let D ( A , B ) denote the minimum r for which Spoiler has a
winning strategy. If such r does not exist, we will write D ( A , B ) = . As it is well known [12], D ( A , B ) r if and only if A
can be distinguished from B by a sentence of quantier rank r in the existential-positive two-variable logic. The existential-
positive fragment of rst-order logic consists of formulas containing only monotone Boolean connectives and only existential
quantiers (thus, negation and universal quantication is forbidden).
Suppose that D ( A , B ) < . We say that Spoiler plays optimally if he never loses an opportunity to win as soon as
possible. More specically, after a round is ended in a position P (determined by the pebbled vertices), Spoiler makes the
next move according to a strategy that allows him to win from the position P in the smallest possible number of rounds.
Note that this move depends only on P and that any Spoilers strategy optimal in the above sense is winning in the r-round
game for r = D ( A , B ).

Lemma 2.1. If Spoiler plays optimally, then the following conditions are true.

1. Spoiler uses the pebbles alternately, say, p in odd and q in even rounds.
2. Whenever Spoiler moves a pebble, he moves it to a new position. That is, if xi V ( A ) denotes the vertex chosen in the i-th round,
then xi +2 = xi . Moreover, if xi +1 = xi , then xi +2 = xi 1 .
3. For all i, (xi , xi +1 ) or (xi +1 , xi ) satises at least one binary relation.

Proof. Recall that a position P in the game is a tuple in V ( A )2 V ( B )2 or in V ( A ) V ( B ) consisting of the currently
pebbled vertices. By assumption, Spoiler has a strategy allowing him to win the game within some number of rounds. Then,
for every P there is an r such that Spoiler has a winning strategy in the r-round game with the initial position P . Denote
the smallest such r by R ( P ). We will denote the vertex of B pebbled by Duplicator in the i-th round by u i .
1. We rst show this for the rst two rounds. Let R denote the minimum number r such that Spoiler has a winning strat-
egy in the r-round game. It is clear that in the rst round Spoiler pebbles a vertex x1 V ( A ) such that maxu V ( B ) R (x1 , u )
is equal to the minimum possible value R 1. If in the second round Spoiler just moves the pebble from x1 to another
vertex x2 , then Duplicator can pebble a vertex u 2 attaining maxu V ( B ) R (x2 , u ) R 1. This allows her to win the next r 2
rounds, contradictory to the fact that the optimal strategy used by Spoiler is winning in the R-round game.
Assume now that Spoiler has used the pebble p in the (i 1)-th round and the pebble q in the i-th round, and the
game is not over yet. By the denition of an optimal strategy, the value R  = maxu R (xi 1 , xi , u i 1 , u ) is minimum possible
among all choices of xi . From now on Spoiler has to win the game in at most r  rounds. If, however, in the (i + 1)-th
round Spoiler uses the pebble q again moving it from xi to xi +1 , then Duplicator can pebble a vertex u i +1 attaining
maxu R (xi 1 , xi +1 , u i 1 , u ) R  . This allows her to win the further R  1 rounds, contradicting Spoilers optimality.
2. The denition of an optimal strategy implies that, after the i-th round is played, Spoiler wins in at most
R (xi 1 , xi , u i 1 , u i ) rounds. Assume that in the (i + 1)-th round Spoiler pebbles xi +1 = xi 1 . Not to lose immediately, Du-
plicator pebbles u i +1 = u i 1 . Starting from the next round, Duplicator is able to stand up in R (xi , xi 1 , u i , u i 1 ) 1 =
R (xi 1 , xi , u i 1 , u i ) 1 rounds, which gives a contradiction.
If xi +1 = xi , the inequality xi +2 = xi 1 follows by a similar argument.
3. Part 1 of the lemma shows that after the i-th round the players actually play the game with the initial position (xi , u i )
(that is, Spoilers optimal strategy can be supposed to be independent of the pair (xi 1 , u i 1 )). In particular, Spoiler has a
strategy allowing him to win the rest of the game in R (xi , u i ) R i rounds, where R is as dened above. Assume that
the vertices xi and xi +1 satisfy no binary relation in A. Then every choice of u i +1 V ( B ) is non-losing for Duplicator in the
 C. Berkholz, O. Verbitsky / Journal of Computer and System Sciences 91 (2018) 104114 107

Fig. 1. The Domino example. (For interpretation of the references to color in this gure, the reader is referred to the web version of this article.)

Fig. 2. An example of Co-Wheels.

(i + 1)-th round. If she chooses u i +1 attaining maxu V ( B ) R (xi +1 , u ) R 1, then she has a strategy allowing her to survive
at least R 1 further rounds after the i-th round, a contradiction. 2

Lemma 2.1 has several useful consequences. The rst of them is that, without loss of generality, we can restrict our
attention to connected structures. Two distinct vertices of a binary structure A are adjacent in its Gaifman graph G A if they
satisfy at least one binary relation of A. Connected components of A are considered with respect to G A . Let A consist of
connected components A 1 , . . . , A k and B consist of connected components B 1 , . . . , B l . Then it easily follows from part 3 of
Lemma 2.1 that D ( A , B ) = mini max j D ( A i , B j ). Another consequence follows from parts 2 and 3.

Corollary 2.2. Suppose that the Gaifman graph G A of A is a tree. If D ( A , B ) < , then D ( A , B ) < 2 v ( A ).

Proof. Consider the existential 2-pebble game on A and B and assume that Spoiler follows an optimal strategy. By part 3
of Lemma 2.1, he all the time moves the pebbles along a path in G A . By part 2 of the lemma, he never turns back. Since
G A is a tree, the game lasts at most 2 d(G A ) + 1 < 2 v ( A ) rounds, where d(G A ) denotes the diameter of G A . 2

Furthermore, we now can state a general upper bound for D ( A , B ).

Corollary 2.3. If D ( A , B ) < , then D ( A , B ) v ( A ) v ( B ) + 1.

Proof. Assume that Spoiler plays optimally. Let xi V ( A ) and u i V ( B ) denote the vertices pebbled in the i-th round. By
part 1 of Lemma 2.1, we can further assume that Spoilers move in the (i + 1)-th round depends only on the (xi , u i ). It
readily follows that, if the game lasts r rounds, then the pairs (x1 , u 1 ), . . . , (xr 1 , u r 1 ) are pairwise different, and hence
r 1 v ( A ) v ( B ). 2

The bound of Corollary 2.3 is tight, at least, up to a factor of 1/2. A suitable lower bound can be obtained from the CSP
instances that appeared in [18,20] under the name of DOMINO problem and were used for benchmarking arc consistency
algorithms. A Domino instance consists of two digraphs A m and B n whose arrows are colored red and blue; see Fig. 1. A m
is a directed cycle of length m with one arrow colored blue and the others red. B n is a blue directed path where red loops
are attached to all its n vertices. Spoiler can win the existential 2-pebble game on A m and B n by moving the pebbles along
the cycle A m , always in the same direction. By Lemma 2.1, this is the only way for him to win in the minimum number
of rounds. When Spoiler passes red edges, Duplicator stays with both pebbles at the same vertex of B n . Only when Spoiler
passes the blue edge, Duplicator passes one (blue) edge forward in B n . Thus, if Duplicator starts playing in the middle of
B n , she survives for at least 12 m(n 1) rounds.

3. More examples of slow constraint propagation

The Domino pairs are remarkable examples of binary structures on which constraint propagation is as slow as possible,
up to a constant factor of 1/2. An important role in the Domino example is played by the fact that we have two different
edge colors. We now show that essentially the same lower bound holds true over a rather restricted class of structures,
namely rooted loopless digraphs, where edges are uncolored, there is a single color for vertices, and only a single root vertex
is colored in it. It is also supposed that every vertex of a rooted digraph is reachable from the root along a directed path.
By the wheel W n we mean the rooted digraph with n + 1 vertices where there are arrows from the root to all the other
n vertices and these vertices form a directed cycle. We call a pair of rooted digraphs G m and H n co-wheels if G m is obtained
from W m by removal of all but one of the arrows from the root and H n is obtained from W n by removal of one arrow from
the root; see an example in Fig. 2.
108 C. Berkholz, O. Verbitsky / Journal of Computer and System Sciences 91 (2018) 104114

Fig. 3. Co-Wheels as colored graphs.

1
Lemma 3.1. Let G m and H n be co-wheels. If m and n are coprime, then D (G m , H n ) < and D (G m , H n ) > 2
m(n 3).

Proof. Let V (G m ) = {xroot , x0 , . . . , xm1 } and V ( H n ) = {aroot , a0 , . . . , an1 }. Assume that x0 is adjacent to the root of G m , a0
is non-adjacent to the root of H n , and the indices increase in the direction of arrows. We rst argue that Spoiler has a
winning strategy in the existential 2-pebble game on G m and H n . Let Spoiler pebble x0 in the rst round. If Duplicator
pebbles the root, then Spoiler wins by pebbling xn1 . Assume that Duplicator responds with at . If t = 0, Spoiler wins by
putting the other pebble on the root. If t > 0, Spoiler is able to force pebbling the pair (x0 , a0 ) in a number of rounds.
Indeed, if Spoiler moves the pebbles alternately along the cycle so that the pebbled vertices are always adjacent, then after
m rounds Spoiler passes the cycle  times and arrives again at x0 , while Duplicator is forced to come to at +m , where the
index is computed modulo n. Since m and n are coprime, m mod n is a generator of the cyclic group Zn . It follows that the
parameter  can be chosen so that t + m = 0 (mod n), and then at +m = a0 .
We now have to show that Duplicator is able to survive at least 12 m(n 3) rounds. When considering the length of
the game, we can assume that Spoiler plays according to an optimal strategy. It follows by Lemma 2.1 that Spoiler begins
playing in a non-root vertex xs and forces pebbling the pair (x0 , a0 ) as explained above, by moving along the cycle always
in the same direction. Let D (xs , at ) denote the minimum number of moves needed for Spoiler to reach this conguration if
Duplicators move in the rst round is at .
Suppose rst that s = 0 and also that Spoiler moves in the direction of arrows. Then he can force pebbling (x0 , a0 ) only
in m moves with  satisfying t + m = 0 (mod n). Denote r = n/2 and let Duplicator choose t = (rm) mod n. Then the
smallest possible positive value of  is equal to r. If Spoiler decides to move in the opposite direction, we have the relation
t m = 0 (mod n), which gives us  n/2. In both cases D (x0 , at ) 12 m(n 1).
Suppose now that s > 0. Let Duplicator pebble at  in the rst round with t  = (t + s) mod n, where t is xed as above.
Note that, from the position (x0 , at ), Spoiler can force the position (xs , at  ) in s moves. Therefore, D (x0 , at ) s + D (xs , at  ),
which implies that D (xs , at  ) D (x0 , at ) (m 1) > 12 m(n 3), as claimed. 2

Theorem 3.2. For every pair of numbers M 5 and N 5, there is a pair of rooted loopless digraphs G and H with v (G ) = M and
v ( H ) = N such that D (G , H ) < and D (G , H ) ( 12 o(1)) M N. Here the o(1)-term is a function of min( M , N ).

Proof. Given co-wheels G m and H n , add k new vertices to G n and  new vertices to H n (and arrows to these vertices from
the roots) and denote the resulting rooted digraphs by G nk by H n . Since the new vertices are useless for both Spoiler and
k
Duplicator, we have D (G m , H n ) = D (G m , H n ) for any k,  0.
Denote m = M 1 and n = N 1. If m and n are coprime, then we can take G = G m , H = H n , and Lemma 3.1 does the
job. Consider now the case that m and n are not coprime. If m is a prime divisor of n, then m and n 1 are coprime, and
we can take G = G m and H = H n11 in this case. The case that n is prime is similar. If none of m and n is prime, let p < n
be the prime closest to n. By [22], we have p > n n0.525 for a large enough n. Assume rst that p does not divide m. Since
n p
these two numbers are coprime, we can take G = G m and H = H p getting

1 1
D (G , H ) = D (G m , H p ) > m ( p 3) > m(n n0.525 3).
2 2
n p
If p divides m, the numbers m 1 and p are coprime, and we take G = G m
1
1 and H = H p . 2

Using a simple gadget, in the Co-Wheels pattern we can make edges undirected simulating directions by vertex colors. In
this way, we can construct examples of pairs with large D (G , H ) also for colored graphs; see Fig. 3.

Corollary 3.3. Theorem 3.2 holds true also for colored undirected graphs with bound D (G , H ) ( 16 o(1)) M N.

Corollary 3.3 can be obtained also from the Domino pattern, though with a smaller factor 18 o(1); see Fig. 4. It is worth
noting that G will be a unicyclic graph while H will be a tree (more exactly, H will be a caterpillar and can be made even
1
a path at he cost of further decreasing the constant factor to 10 o(1)). Note that this result is best possible in the sense
that, by Corollary 2.2, G cannot be a acyclic.

Corollary 3.4. For every M 3 there is a unicyclic colored graph G M with M vertices and for every N 1 there is a tree H N with N
vertices such that D (G M , H N ) < and D (G M , H N ) > 18 ( M 1)( N 5).
 C. Berkholz, O. Verbitsky / Journal of Computer and System Sciences 91 (2018) 104114 109

Fig. 4. The colored graphs obtained from the Domino example in Fig. 1.

Fig. 5. Co-Wheels as dags.

Remark 3.5. Feder and Vardi [1] showed that a general CSP is equivalent to the homomorphism problem restricted to
directed acyclic graphs (dags). In view of this result, it is natural that Corollary 3.3 is true also for uncolored dags. Indeed,
the directed cycles in Co-Wheels can be broken by subdividing each arrow in the cycle into three arrows oriented in different
directions. The root nodes can be designated by attaching additional arrows; see Fig. 5. In fact, any distinguishable uncolored
digraphs G and H with large D (G , H ) must be acyclic: The existence of a directed cycle or a loop in G or H implies that
either D (G , H ) = or D (G , H ) v ( H ) + 1.
Note also that Corollary 3.3 has no analog for uncolored undirected graphs. Using the methods of [23, Section 7], one
can show that, in this case, either D (G , H ) = or D (G , H ) 2 v ( H ).

4. Winner proof systems

Inspired by [24], we now introduce a notion that allows us to dene a few useful parameters measuring the speed of
constraint propagation. In the next section it will serve as a link between the length of the existential 2-pebble game on
( A , B ) and the running time of an AC algorithm on input ( A , B ). Below, N (x) denotes the set of vertices adjacent to a
vertex x.
Let G and H be connected colored graphs, both with at least 2 vertices. A proof system of Spoilers win on (G , H ) consists of
axioms, that are pairs ( y , b) V (G ) V ( H ) with y and b colored differently, and derivations of pairs (x, a) V (G ) V ( H )
and a special symbol by the following rules:

(x, a) is derivable from any set { y } N (a) such that y N (x);

is derivable from a set { y } V ( H ).

A proof is a sequence P = p 1 , . . . , p +1 such that if i , then p i V (G ) V ( H ) and it is either an axiom or is derived from
a set { p i 1 , . . . , p i s } of preceding pairs p i j ; also, p +1 = is derived from a set of preceding elements of P . More precisely,
we regard P as a dag on  + 1 nodes where a derived p i sends arrows to each p i j used in its derivation. Moreover, we
always assume that P contains a directed path from to each node, that is, every element of P is used while deriving .
We dene the length and the size of the proof P as length( P ) = v ( P ) 1 and size( P ) = e ( P ) respectively. Note that
length( P ) is equal to , the total number of axioms and intermediate derivations in the proof. Since it is supposed that the
Gaifman graph of P is connected, we have length( P ) size( P ), with equality exactly when P is a tree. The depth of P will
be denoted by depth( P ) and dened to be the length of a longest directed path in P . Obviously, depth( P ) length( P ).
It is easy to show that a proof P exists iff D (G , H ) < (see part 1 of Theorem 4.1 below). Given such G and H , dene
the (proof) depth of (G , H ) to be the minimum depth of a proof for Spoilers win on (G , H ). The (proof) length and the
(proof) size of (G , H ) are dened similarly. We denote the three parameters by depth(G , H ), length(G , H ), and size(G , H ),
respectively. Note that depth(G , H ) length(G , H ) size(G , H ).

Theorem 4.1. Let G and H be connected colored graphs, both with at least 2 vertices, such that D (G , H ) < .

1. depth(G , H ) = D (G , H ).
2. depth(G , H ) length(G , H ) v (G ) v ( H ) and this is tight up to a constant factor: for every pair of integers M , N 2 there is a
pair of colored graphs G , H with v (G ) = M and v ( H ) = N such that depth(G , H ) ( 16 o(1)) M N.
3. size(G , H ) < 2 v (G )e ( H ) + v ( H ).
1
4. For every N there is a pair of colored graphs G N and H N both with N vertices such that size(G N , H N ) > 128 N 3 for all large
enough N.
110 C. Berkholz, O. Verbitsky / Journal of Computer and System Sciences 91 (2018) 104114

Note that part 3 implies that size(G , H ) < N 3 if both G and H have N vertices. Therefore, part 4 shows that the upper
bound of part 3 is tight up to a constant factor.

Proof. 1. It suces to prove that, for every r 0, Spoiler has a strategy allowing him to win in at most r rounds starting
from the position (x, a) if and only if the pair (x, a) is derivable with depth r. This equivalence follows by a simple inductive
argument on r.
2. The upper bound on depth(G , H ) follows from a simple observation that any proof can be rewritten so that every
axiom used and every derived pair appears in it exactly once. The lower bound follows by part 1 from Corollary 3.3.
3. Consider a proof P where each pair (x, a) appears at most once. Since the derivation of (x, a) contributes deg a arrows
in P , and the derivation of contributes v ( H ) arrows, we have
 
size( P ) < deg a + v ( H ) = v (G ) deg a + v ( H ) = 2 v (G )e ( H ) + v ( H ).
(x,a) a

The inequality is strict because there must be at least one axiom node, which has out-degree 0.
4. Note that size(G , H ) depth(G , H )( H ), where ( H ) denotes the minimum vertex degree of H . Therefore, we can take
graphs G and H with almost the same number of vertices and with quadratic depth(G , H ), and make ( H ) large by adding
linearly many universal vertices of a new color to each of the graphs. A universal vertex is adjacent to all other vertices in
the graph. If each of the graphs receives at least two new vertices, they have no inuence on the duration of the existential
2-pebble game.
More specically, we use the co-wheels from Lemma 3.1 with coprime parameters m = n 1 converted to colored graphs
as in Corollary 3.3; see Fig. 3. Thus, we have colored graphs G and H with v (G ) = 3n 2 and v ( H ) = 3n + 1 such that
D (G , H ) > 12 (n 1)(n 3). Add green universal vertices so that the number of vertices in each graph becomes N =  92 n.
1
For the new graphs G N and H N we still have D (G N , H N ) > 2
(n 1)(n 3) while now ( H N ) 32 n. 2

Remark 4.2. In general, the proof depth can be much smaller than the proof length. In fact, for every n there are two
colored graphs G and H with v (G ) = n + 1 and v ( H ) = 2n such that depth(G , H ) = 2 and length(G , H ) = n2 . For example,
let G be the star K 1,n with all vertices colored differently. Let the central vertex be colored in red. In order to construct H ,
begin with the complete bipartite graph K n,n where one part of vertices is colored completely in red and the other part is
colored as the set of leaves in G. To obtain G, we remove a matching (n pairwise non-adjacent edges) from this graph. Here
we use n + 1 colors. This number can be made xed similarly to [2, Section 3.6].

5. Time complexity of arc consistency

5.1. Reduction to colored graphs

In this subsection we justify our focusing on colored graphs by showing a linear time reduction from the AC-Problem to
its restriction on colored simple connected graphs (that also preserves the parameter D ( A , B )). The size of aA binary structure
A with binary relations E 1 , E 2 , . . . and unary relations U 1 , U 2 , . . . is dened to be || A || = i | E iA | + j | U j |.

Lemma 5.1. There is a linear time reduction that takes two relational structures A and B with arbitrary unary and binary relations
and computes two colored simple connected graphs G and H such that

A and B pass the arc consistency test iff so do G and H ,

D (G , H ) = ( D ( A , B )),
v (G ) = O ( A ), e (G ) = O ( A ),
v ( H ) = O ( B ), e ( H ) = O ( B ).

Proof. For every binary relation R we introduce two new vertex colors light-R and dark-R and replace every pair (x, y ) R
in A or B by an undirected path (x, r , r  , y ) where r is colored light-R and r  is colored dark-R. Each triple x, y , R is handled
by its own pair r , r  . Note that a loop (x, x) R gives rise to a cycle (x, r , r  ) of length 3.
We also have to ensure that the vertex colors in G and H are disjoint even if the unary relations in A and B overlap. To
this end, for every unary relation U and vertex x U in A or B we remove x from U but create a new vertex s U adjacent
to x.
In order to get the graphs connected, add a single vertex with a new color to both graphs and connect it with all other
vertices. 2

5.2. An upper bound

We now establish an upper bound of O ( v (G )e ( H ) + e (G ) v ( H )) for the time complexity of the AC-Problem. One way to
obtain this result is to use the linear-time reduction from arc consistency to the satisability problem for propositional Horn
 C. Berkholz, O. Verbitsky / Journal of Computer and System Sciences 91 (2018) 104114 111

clauses (Horn-Sat) presented by Kasif [25]. The reduction transforms the input graphs G and H into a propositional Horn
formula of size v (G )e ( H ) + e (G ) v ( H ) that is satisable iff arc consistency can be established on G and H . The upper bound
then follows by applying any linear time Horn-Sat algorithm. Going a different way, we here show that the same bound
can be achieved by a propagation-based algorithm, that we call AC13. On the one hand, AC13 does much the same of what
a linear time Horn-Sat solver would do (after applying Kasifs reduction). On the other hand, it can be seen as a slightly
accelerated version of the algorithm AC-4 [6].

Algorithm 1 AC13.
Input: Two colored connected graphs G and H .
/*INITIALIZATION*/
Let Q be an empty queue.
for all x V (G ) do
D x {a V ( H ) | a has the same color as x};
if D x = then return reject;
for all x V (G ), a V ( H ) do
counter[x,a] deg a;
if a
/ D x then add (x, a) to Q ;
/*PROPAGATION*/
while Q not empty do
Select and remove (x, a) from Q ;
for all b N (a) do
counter[x,b ] counter[x,b ]1;
if counter[ x,b ]= 0 then
for all y N (x) do
if b D y then
Delete b from D y ;
Add ( y , b) to Q ;
if D y = then return reject;
end while
return accept;

Theorem 5.2. AC13 solves the AC-Problem in time O ( v (G )e ( H ) + e (G ) v ( H )).

Proof. We rst analyze the running time. The initialization phase requires O ( v (G ) v ( H )). The propagation phase takes deg a
steps for every (x, a) Q and deg x steps for every (x, b) such that counter[x,b ] gets 0. Since every pair is only put
once
 on the queue and every counter voids out only once the total running time of the propagation phase is bounded by
(x,a) V (G ) V ( H ) (deg x + deg a) = v (G )e ( H ) + e (G ) v ( H ).
The rest is devoted to the proof of the algorithms correctness. Translated into the language of the existential 2-pebble
game, the problem is to decide for a given pair of colored graphs G and H which of two cases occurs: Spoiler has a
winning strategy for some number of rounds or Duplicator has a winning strategy for any number of rounds. Simplifying
the terminology, we will say that Spoiler wins in the former case and Duplicator wins in the latter case. We begin with
auxiliary notions and claims, then show that a modied version of the algorithm is correct, and nally come back to the
original version.
Given a pair (x, a) V (G ) V ( H ), we denote the existential 2-pebble game with the initial position (x, a) by Game(x, a).
Suppose that S  V (G ) V ( H ) is a set of pairs (x, a) such that Spoiler wins the game Game(x, a). We will assume that S
contains all pairs of differently colored vertices.
Let ( y , b) / S. Given x V (G ) and a V ( H ), we call a a partial x-certicate for ( y , b) if y N (x), b N (a), and (x, a) S.
Assuming y N (x), we denote the set of all partial x-certicates for ( y , b) by Cert y (x, b). Note that Cert y (x, b) = S |x N (b),
where S |x = { a V ( H ) : (x, a) S } is the x-slice of S. It follows that

Cert y (x, b) = Cert y  (x, b) for any two y , y  N (x), (1)

that is, Cert y (x, b) actually does not depend on y.

Furthermore, call x a complete certicate for ( y , b) if Cert y (x, b) = N (b). The rst of two following claims is straightfor-
ward.

Claim A. If ( y , b) has a complete certicate, then Spoiler wins Game( y , b).

Claim B. Let G be connected. If Spoiler wins the existential 2-pebble game on G and H , then there exists a pair ( y , b)
/S
having a complete certicate.

Proof of Claim B. Assume that no ( y , b)

/ S has a complete certicate and show that then Duplicator wins the game on G
and H .
112 C. Berkholz, O. Verbitsky / Journal of Computer and System Sciences 91 (2018) 104114

Call a vertex x V (G ) complete if S |x = V ( H ). Under the assumption made, no vertex of G is complete. Indeed, if x
is complete, then any adjacent to it vertex y must be complete too because otherwise we would have ( y , b) / S for some
b V ( H ) and then x would be a complete certicate for ( y , b), contradictory to the assumption. It follows by connectedness
of G, that S = V (G ) V ( H ) while S is supposed to be a proper subset.
The absence of complete vertices leads to the following winning strategy for Duplicator. Assume that Spoiler pebbles a
vertex y in the rst round. Duplicator responds with a vertex b such that ( y , b) / S. Such b exists since b is not complete.
Let Spoiler pebble a vertex x in the next round. If x and y are non-adjacent, Duplicator responds similarly (with a vertex
a such that (x, a)
/ S). If x and y are adjacent, then Duplicator responds with a vertex a adjacent to b such that (x, a) / S.
Such a exists because otherwise x would be a complete certicate for ( y , b). Each subsequent round is played similarly. 2

We are now ready to describe an algorithm solving the existential 2-pebble game on connected colored graphs G and H .
We will maintain a set S V (G ) V ( H ) of pairs (x, a) for which it is for sure known (certied) that Spoiler wins Game(x, a).
Initially, S consists of those (x, a) with x and a colored differently. Our algorithm will try step by step to extend S. If no
extention is possible any more, the algorithm decides that Spoiler wins if S reaches the full product V (G ) V ( H ) and that
Duplicator wins if S stays its proper subset.
Each time S will be extended with a pair ( y , b) / S having a complete certicate. Note that the correctness of this
procedure is ensured by Claims A and B. By Claim B, an extension is always possible if Spoiler wins. Thus, if Spoiler wins,
the algorithms decision will be correct because then eventually S = V (G ) V ( H ). On the other hand, Claim A implies that
S consists of positions winning for Spoiler. Therefore, if S = V (G ) V ( H ), then Spoiler really has a winning strategy in the
game on G and H .
We now explain how our algorithms nds a pair ( y , b) / S with a complete certicate. For this purpose, another set
Q S is maintained. This set consists of inuential pairs (x, a) S producing a partial x-certicate for at least one pair
( y , b)
/ S. Initially, Q = S is the set of pairs of differently colored vertices. For each ( y , b) / S and x V (G ), we also
have a counter c y (x, b) for the number of vertices a N (b) that are still not accepted as a partial x-certicate for ( y , b).
Initially, c y (x, b) = deg b. The algorithm updates S as follows. It takes an arbitrary pair (x, a) Q and accepts a as a partial
x-certicate for all ( y , b) such that y N (x) and b N (a) by decreasing the value of c y (x, b) in 1. After this is done, the pair
(x, a) is not inuential any more and is removed from Q . Once c y (x, b) = 0 for some (x, b), this pair receives a complete
certicate, namely x, and is added to both S and Q . This completes description of our algorithms.
The algorithm AC13 is pretty close to the slightly simplied version we just described. Instead of S, AC13 maintains
the set D x = V ( H ) \ S |x for each x V (G ) and terminates as soon as D x = for some x. Moreover, the counter c y (x, b) is
parametrized only by x and b, which is justied by the equality (1). 2

5.3. Lower bounds

Recall that by a propagation-based arc consistency algorithm we mean an algorithm that solves the AC-Problem by iteratively
deleting possible assignments a to a variable x from the domain D x according to the arc consistency rule and rejects iff one
domain gets empty. Let us maintain a list L of deleted variablevalue pairs by putting a pair (x, a) there once a is deleted
from D x . If the algorithm detects arc inconsistency, then it is evident that L, prepended with axioms and appended with
, forms a proof of Spoilers win. Thus, a propagation-based arc consistency algorithm can be viewed as a proof search
algorithm that produces (in passing) a proof P of Spoilers win. This situation is related to the concept of a certifying
algorithm [26]: Propagation-based algorithms not only detect Spoilers win but also produce its certicate. For every derived
element of P , an algorithm has to recognize its already derived parents. This allows us to relate the running time to the
proof size. Specically, given an arbitrary propagation-based algorithm for the AC-Problem, let time(G , H ) denote the time it
takes on input (G , H ). If the input (G , H ) is arc inconsistent, then it holds
time(G , H ) size(G , H ). (2)

Theorem 5.3. Fix an arbitrary propagation-based algorithm.

1. Let T 1 (k, ) denote the worst-case running time of this algorithm over colored graphs G and H with e (G ) = k and e ( H ) = . Then
T 1 (k, ) > 18 (k 1)( 4) for all k and .
1
2. Let T 2 (n) denote the worst-case running time of the algorithm on inputs (G , H ) with v (G ) + v ( H ) = n. Then T 2 (n) > 16
n3 for
all large enough n.

Proof. By Corollary 3.4, there are colored graphs G k with e (G k ) = v (G k ) = k and H  with e ( H  ) = v ( H  ) 1 =  for which
1
8
(k 1)( 4) < D (G k , H  ) < . By the relation (2), on input (G k , H  ) the algorithm takes time at least size(G k , H  ), for
which we have size(G k , H  ) depth(G k , H  ) = D (G k , H  ) by part 1 of Theorem 4.1.
Part 2 follows from part 4 of Theorem 4.1. 2

Corollary 5.4. In terms of the parameters e (G ) and e ( H ), the time bound O (e (G ) e ( H )) is optimal up to a constant factor among
propagation-based algorithms.
 C. Berkholz, O. Verbitsky / Journal of Computer and System Sciences 91 (2018) 104114 113

Note that O (e (G ) v ( H ) + v (G )e ( H )) = O (( v (G ) + v ( H ))3 ).

Corollary 5.5. In terms of the parameter n = v (G ) + v ( H ), the time bound O (n3 ) is best possible for a propagation-based algorithm.

5.4. Parallel complexity

It is known that the AC-Problem is PTIME-complete under logspace reductions [25,14]. Under the assumption that PTIME
= NC, it follows that the AC-Problem cannot be parallelized. However, several parallel algorithms with a polynomial num-
ber of processors appear in the literature (e.g., [19]). We are able to show a tight connection between the running time
of a parallel algorithm and the round complexity of the existential 2-pebble game. The following result is worth noting
since D (G , H ) = depth(G , H ) can be much smaller that size(G , H ) (cf. Remark 4.2), and then a parallel propagation-based
algorithm can be much faster than any sequential propagation-based algorithm.

Theorem 5.6.

1. AC-Problem can be solved in time O ( D (G , H )) on a CRCW-PRAM with polynomially many processors.

2. Any parallel propagation-based arc consistency algorithm needs time D (G , H ) on arc inconsistent instances (G , H ).

Proof. First apply the reduction from Lemma 5.1 to colored simple graphs in constant parallel time. Consider the parallelized
version of AC-graph and assume that Spoiler wins the existential 2-pebble game on G and H . The initialization phase can
be implemented in constant time. For every element (x, a) Q the propagation phase can also be processed in constant
time. The algorithm iteratively processes the whole set Q in parallel constant 
 time and computes a new set Q . Let Q i
be the queue Q after the ith iteration of the propagation phase and Q i := j i Q j . An easy induction shows that Q i
(for i < D (G , H )) is the set of all positions (x, a) V (G ) V ( H ) such that Spoiler wins in at most i steps. Hence, for
 = D (G , H ) 1 it holds that {x} V ( H ) Q  where x is the rst vertex Spoiler puts a pebble on. But this means that in
iteration  all values from D x are already deleted and hence the algorithm rejects.
A parallel propagation-based algorithm produces proofs of Spoilers win. Hence, the algorithm can derive (x, a) only if
the parents in the underlying proof have been derived. It follows that the parallel running time has to be lower bounded by
depth(G , H ) = D (G , H ). 2

6. Conclusion

We investigated the round complexity D (G , H ) = D 2 (G , H ) of the existential 2-pebble game on colored graphs and
established lower bounds of the form ( v (G ) v ( H )), which translate to lower bounds on the nested propagation steps in arc
consistency algorithms. In a subsequent work [27] this lower bound has been extended to a round lower bound of the form
D k (G , H ) = ( v (G )k1 v ( H )k1 ) for the existential k-pebble game. As this game interacts with k-consistency algorithms in
the same way as the 2-pebble game with arc consistency, this lower bound implies a lower bound for propagation-based
sequential and parallel k-consistency algorithms and nearly matches the trivial O ( v (G )k v ( H )k ) upper bound on the runtime.
Finally, we want to stress that our lower bounds for the time complexity of arc consistency hold only for constraint
propagation-based algorithms. Is there a faster way to solve the AC-Problem using a different approach?

References

[1] T. Feder, M.Y. Vardi, The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory,
SIAM J. Comput. 28 (1) (1998) 57104.
[2] C. Berkholz, Lower bounds for existential pebble games and k-consistency tests, Log. Methods Comput. Sci. 9 (4) (2013) 123.
[3] A.K. Mackworth, Consistency in networks of relations, Artif. Intell. 8 (1) (1977) 99118.
[4] C. Bessire, Handbook of Constraint Programming, Elsevier, Amsterdam, 2006, pp. 2984, Ch. Constraint Propagation.
[5] M.R.C.v. Dongen, AC-3d an ecient arc-consistency algorithm with a low space-complexity, in: Proc. Principles and Practice of Constraint Programming
2002, CP02, in: LNCS, vol. 2470, Springer, Heidelberg, 2002, pp. 755760.
[6] R. Mohr, T.C. Henderson, Arc and path consistency revisited, Artif. Intell. 28 (2) (1986) 225233.
[7] P.V. Hentenryck, Y. Deville, C.-M. Teng, A generic arc-consistency algorithm and its specializations, Artif. Intell. 57 (1992) 291321.
[8] C. Bessire, Arc-consistency and arc-consistency again, Artif. Intell. 65 (1) (1994) 179190.
[9] C. Bessire, E.C. Freuder, J.-C. Regin, Using constraint metaknowledge to reduce arc consistency computation, Artif. Intell. 107 (1) (1999) 125148.
[10] A. Chmeiss, P. Jegou, Ecient path-consistency propagation, Int. J. Artif. Intell. Tools 07 (02) (1998) 121142.
[11] J.-C. Rgin, AC-*: a congurable, generic and adaptive arc consistency algorithm, in: P. van Beek (Ed.), Principles and Practice of Constraint Programming
2005, CP05, in: LNCS, vol. 3709, Springer, Heidelberg, 2005, pp. 505519.
[12] P.G. Kolaitis, M.Y. Vardi, On the expressive power of datalog: tools and a case study, J. Comput. Syst. Sci. 51 (1) (1995) 110134.
[13] P.G. Kolaitis, M.Y. Vardi, A game-theoretic approach to constraint satisfaction, in: H.A. Kautz, B.W. Porter (Eds.), AAAI/IAAI 2000, AAAI Press/The MIT
Press, California, 2000, pp. 175181.
[14] P.G. Kolaitis, J. Panttaja, On the complexity of existential pebble games, in: M. Baaz, J.A. Makowsky (Eds.), Computer Science Logic 2003, CSL 2003, in:
LNCS, vol. 2803, Springer, Heidelberg, 2003, pp. 314329.
[15] A. Atserias, A.A. Bulatov, V. Dalmau, On the power of k -consistency, in: L. Arge, C. Cachin, T. Jurdzinski, A. Tarlecki (Eds.), ICALP 2007, in: LNCS,
vol. 4596, Springer, Heidelberg, 2007, pp. 279290.
114 C. Berkholz, O. Verbitsky / Journal of Computer and System Sciences 91 (2018) 104114

[16] A. Atserias, V. Dalmau, A combinatorial characterization of resolution width, J. Comput. Syst. Sci. 74 (3) (2008) 323334.
[17] C. Berkholz, On the complexity of nding narrow proofs, in: FOCS 2012, IEEE Computer Society, Los Alamitos, CA, USA, 2012, pp. 351360.
[18] R. Dechter, J. Pearl, A Problem Simplication Approach that Generates Heuristics for Constraint-Satisfaction Problems, Tech. rep., Cognitive Systems
Laboratory, Computer Science Department, University of California, Los Angeles, 1985.
[19] A. Samal, T. Henderson, Parallel consistent labeling algorithms, Int. J. Parallel Program. 16 (1987) 341364.
[20] C. Bessire, J.-C. Rgin, R.H.C. Yap, Y. Zhang, An optimal coarse-grained arc consistency algorithm, Artif. Intell. 165 (2) (2005) 165185.
[21] C. Berkholz, O. Verbitsky, On the speed of constraint propagation and the time complexity of arc consistency testing, in: K. Chatterjee, J. Sgall (Eds.),
Proceedings, Mathematical Foundations of Computer Science 2013, MFCS13, in: LNCS, vol. 8087, Springer, 2013, pp. 159170.
[22] R. Baker, G. Harman, J. Pintz, The difference between consecutive primes. II, Proc. Lond. Math. Soc., Ser. III 83 (3) (2001) 532562.
[23] C. Berkholz, A. Krebs, O. Verbitsky, Bounds for the quantier depth in nite-variable logics: Alternation hierarchy, ACM Trans. Comput. Log. 16 (3)
(2015) 21:121:26.
[24] A. Atserias, P. Kolaitis, M. Vardi, Constraint propagation as a proof system, in: M. Wallace (Ed.), Principles and Practice of Constraint Programming
2004, CP04, in: LNCS, vol. 3258, Springer, Heidelberg, 2004, pp. 7791.
[25] S. Kasif, On the parallel complexity of discrete relaxation in constraint satisfaction networks, Artif. Intell. 45 (3) (1990) 275286.
[26] R.M. McConnell, K. Mehlhorn, S. Nher, P. Schweitzer, Certifying algorithms, Comput. Sci. Rev. 5 (2) (2011) 119161.
[27] C. Berkholz, The propagation depth of local consistency, in: Proceedings of the 20th International Conference on Principles and Practice of Constraint
Programming, CP 2014, 2014, pp. 158173.