A New Method for Solving Constraint Satisfaction Problems

ABSTRAcr

This paper deals with the combinatorial search problem of finding values for a set of variables subject to a set of constraints. This problem is

referred to as a constraint satisfaction problem.

We present an algorithm for finding all the solutions of a constraint satisfaction problem with worst case time bound O(m*kf+l) and space bound O(n*kf+1), where n is the number of variables in the problem, m the number of constraints, k the cardinality of the domain of the variables, and f <n an integer depending only on a graph which is associated with the problem. It will be shown that for planar graphs and graphs of fixed genus this f is O(/nJ.

I. INI'RODOCTIOO

Many problems in diverse fields of computer science can be formulated as constraint satisfaction problems: a number of variables (sometimes called units) are to be assigned values (labels), such that certain given constraints on subsets of these variables are satisfied. Instances of constraint satisfaction problems range from graph theory and automata theory problems, like graph oolouring and autanata haoc.m:>rphism, to problems in AI such as scene analysis and combinatorial puzzles. FOr representative examples see [4). Problems involving more general

constraints are treated in [6].

Algorithms to solve these problems usually rely on backtracking and/or on some forms of relaxation methods or look-ahead operators ( [1], [3], [12], [10], [2], [4], [5], [9]). All these algorithms seem to work well most of the time. But they can behave badly in some cases and oo rot alla.r a tight worst case analysis. This is not surprising as Montanari [11] showed that the general constraint satisfaction problem is

NP-complete.

One of the reasons why backtrack algorithms have a potentially bad behaviour is the fact that they use a minimal amount of space. ct>serve for instance, that a simple exhaustive backtrack search has an exponential running time oot uses onlv a linear amount of space. One can view the relaxation methods and look-ahead operators proposed in the literature as attempts to invest in

A NEW METHOD FOR SOLVING

CONSTRAI~ SATISFACTION PROBLH1S

Raimund Se idel

Depa rtment ,,f Comput('r Science University of British Columbia

space in order to save time.

In the ~olla.~ing sections we develop an algorithm which invests in space heavily. Usina the termirology of backtrack search and search trees one can say that the saving in time is achieved by identifying initial segments of a search tree which are effectively identical, that is, they differ only on variables which oo not constrain the remaining uninstantiated variables . However, we found it advantageous to formulate our algorithm rot in terms · of backtrack search but using the concept of dynamic progranming. Thus in contrast to other methods, our algorithm permits easy analysis of its time and space complexity.

I I · THE PROOLEl-1

A constraint satisfaction problem (CSP) can be defined as follCMS: given is a set of variables x1 , ·.· ,Xn and associated with each variable Xi a dana in D1 of values. Furthermore, on sane subsets of the variables constraints are given, limiting possible value tuples for those variables. A soluti~n of a CSP is an n-tuple of values (au···~~)£ (\x:-=-:-~, which simultaneously satisfies all g1ven constraints. The orm5lete set of solutions of a CSP is the subset o otx ..· xDn, campr1s1ng exactry-a~the solutions. A CSP is called unsatisfiable if its complete set of solutions 1s empty.

FOr our purposes all domains are finite. We also assume that the domains of all n variables are of equal cardinality, IDtl=k for i=l, ·.· ,n. We shall see later on, that this assllllption is just a convenience for the sake of analysis and by no means vital to the alqorithm to be proposed.

Furthermore we will restrict our attention to CSPs involving only binary constraints. This restriction seems more critical. But it will be seen that the method to be presented can be awlied to general CSPs without much modification.

Montanari [ll] pointed out that a CSP only involving binary constraints can be represented by a graph. Let us call it the constraint graph. Each of its vertices corresponds to a variaEie. Two vertices are adjacent iff there is a constraint between the corresponding two variables. In the folla.ring we will feel free to call a vertex a variable or vice versa, or to identify edges with constraints.

III. A SIMPLE EXAMPLE

Let us look at the foll<=Ming exarrq:>le. Let us assume we have a CSP involving 10 variables and 19 binary oonstraints, and it can be represented by the constraint gra{il given in figure l. Let c 1 j be the constraint between variables Xi and Xj ·

We can find out whether such a CSP is satisfiable in the foll<=Ming way:

Create a ternary constraint relation c123 for X1 , x2 , and x3 which comprises all value triples for those variables allt::Med by C12 and C13. Next, using c123 construct a ternary constraint relation c234 which comprises all value triples for x2 ,X3 I and X,. which permit a value for X1 , such that C1 2 , C13 , C14 ,C24 , and C34 are satisfied. Note that, as indicated in figure2 by the shaded lines, X2 ,X3 , and ~ "cut" the constraint graph and thus all of the influence of X1 on the CSP is subsumed by c234 and therefore Xl I C14 I C24 I CJ4 I and C123 are of no ~rtance any more. (This is indicated by the dashed lines in figure 2.) Aloo note that if c234 is empty the CSP must be unsatisfiable.

In the same manner, we construct using C234 a ternary relation C345 for X3 , X4 , and Xs , which comprises all value triples allowed by C34 and C45 , and permits values for X1 and x2· Again, if C345 is empty the CSP must be unsatisfiable and we can stop. Otherwise we continue in the same way and construct ternary relations C456 , Cs67 ; c678 I c789 and c8910 · If any of those relations is empty, the CSP is unsatisfiable. If Cs910 is nonempty we can generate a general oolution for the CSP by using the created ternary constraints and instantiating the variables in the reverse order to the order in which they were discarded.

If each of the variables x 1 can assume k different values, then any of the ternary relations above can have at most k3 elements. 'Iherefore onlv k4 combinations of value triples and values need bo be considered for the construction of a new ternary relation. Hence a CSP representable by such a graph can be decided in O(k4) steps. Note that this worst case complexity is completely independent of the specific instances of the constraint relations Cij·

IV. THE INIJASICN PRIXEIX.JRE

In order to describe, ha.l the method outlined above can be generalized so that it can be ar:plied to an arbitrary constraint gra{il, we need a fEW definitions.

Given an n-vertex graph G, call a sequence (Gi), i=l, ··· ,n, of induced subgraphs of G, where the number of vertices in G. is i and G. is a subgra{il of Gi+l, an inv~sion of G. We ~11 the set F1 of vertices of G 1 which -are adjacent to vertices not in G 1 the front of Gi· Vertices in GcF1 are called oonquered verTices. The front ~ !J of ~i 1s the number of vertices in F i. Therront length of an invasion is the maximum front length of the subgraphs G 1 involved. An invasion of a graph G is called optimal if its front length is not greater than the front length of any other invasion of G.

Given an invasion {G 1 }, i=l, ... ,n, of a constraint graph G, we claim that satisfiability of a corresponding CSP can be decided by the procedure outlined belCM:

FOr i=l to n inductively find all value tuples for the front vertices F 1 of Gi which are consistent with one of the allowed value tuples of F1_1. If there are no such tuples, stop and report the CSP unsatisfiable.

The correctness of this algorithm foll<=Ms by induction using two observations:

Let <X1, ·.. ,Xi> be the i-tuple of the vertices in Gi arranged in a way such that X1, ··. ,Xfi are the vertices in Fi.

1. The conquered vertices Xfi+1····,Xi are not involved in constraints with variables not in Gi·
2. ii) <a1, ··· ,af. > is made a valid labeling tuple for the veftices in Fi if and only if there are . values af 1 +1, .· ,ai for the conqu:red vert1ces Xfi+1, .. ,Xi such that <a1, ··· ,ai>1s a valid labeling for the vertices in Gi, i.e. <a1, ... ,ai> satisfies all constraints within Gi.

v. HCW 'IO ~ ALL SOimiCNS OF A CSP

Given an invasion {Gi}, i=l, ··· ,n, for the constraint graph of a CSP, the above procedure just answers the question whether the CSP is satisfiable. But it can be Urt>roved to render a graph which represents the complete set of solutions of the CSP. Call this graph the solution ~ of a CSP with respect to invasion { Gi} · nus solution graph is a circuit-free directed multigraph with labeled arcs. (Tb avoid confusion let us use the terms node and arc for the solution graph, and the terms vertex and edge for the constraint graph.) It has ~ distinguished nodes such that the set of directed paths between these ~ nodes corresporrls one to one with the complete set of solutions of the CSP.

Consider the following simple example: four variables X1, ... ,X4 are given; each variable is to be assigned an integer between 1 and 3 such that the constraints X1 <X2 , x1 <X 3 , X 2 <Xq , and x 3 <Xq hold. Figure 3 shows the constraint graph G for this CSP, Figure 4 shows the solution graph with respect to the invasion {Gil Gi is the subgraph of G irrluced by the vertices JS , ~i }. The labels along the directed paths fran 54 to sa represent all the solutions for this CSP.

possible labelings for the front of G 1 <X 1 >

oossible labelings for the front of G 2 <Xl ,X 2 >

We are rt::M ready to state an improved version of the invasion procedure which constructs the solution graph of a CSP with respect to a given invasion.

Assume a CSP with n variables involving only binary constraints is given. For its constraint graph an invasion {Git· i=l, .·. ,n, is given. Let Go be the errpty set and let Xi be the single vertex of Gi-Gi -1·

Furthermore let si , i=l, .·· ,n, be disjoint sets of nodes of the solution graph. The elements of s 1 shall be named by labeling tuples of the front vertices Fi of Gi. (By. convention let there be only one labeling tuple for an empty set of variables. Thus, if F1 is empty, Si contains at most one element, let us call it si.)

Initially Si is errpty for i=l, ··· ,n. So is set to { sa } · For i=l to n do:

Fbr each value tuple a in s 1 _ 1 and for each value c of x1 whose combination satisfies all constraints between the vertices in Fi-1 and xi do:

Let b be the resulting value tuple for the vertices in Fi·

Set si to the union of s1 and { b} · Construct an arc fran b to a and label it with c.

possible labelinqs for the front of G 3 <X 2 ,x 3 > possible labelings for the front of G4 <>

CLaim:

~----The above procedure yields a circuit-free directed multigraph.

2. The tuple <a1, ··· ,an> is a solution of the CSP if and only if there is a directed path fran sn to s0 whose arc label sequence is an, ··· ,a1·

Proof:

~e solution graph is circuit-free because for all i and j, i I j, Si and s j are disjoint and there are only arcs fran nodes in si to nodes in 5;_1. It is possible to have more than one arc between a node in si and a node in si-l in the case that X; is not a front vertex of Gi .

2. This statement follows from the inductive argument that the set of paths between a node <a1, ·.. ,a~i > in Si and s0 represents exactly all the solut1ons of the CSP restricted to Gi which have a1, .·. ,ar . as instantiation of the front

Q.E.D.

vertices of G1· 1

It is now natural to ask about the complexity of this procedure. The folla,..ring theorem gives an answer to this question. It is assumed that it takes constant time to determine whether two variables satisfy a common constraint.

Theorem:

Given is a CSP involving m binary constraints on n variables. Each of the variables can take on k different values. FOr the constraint graph of the CSP an invasion (Gi}, i=l, ··· ,n, with front length f is given.

The above algorithms produces a solution graph of the CSP in time at most O(m*kf+l) and uses space at most O(n*kf+l).

Proof:

s ._1 can not have more than kfi-1 ~ kf elements. T~us at most kf+l combinations are possible between elements of Si-1 and values of X;. Therefore there can not be more than kf+l arcs fran nodes in S; to nodes in S i _ 1 · So the algorithm uses space O(n*kf+l ).

For each i at most f binary constraints need to be checked for each of the at most kf+l combinations between elements in Si-1 and values of Xi. Therefore there are not more than n*f*kf+l checks. But overall there exist only m constraints. Thus only m*k f+l checks are necessary, and the algorithm uses time O(m*kf+l).

Q.E.D.

Implementation of this procedure should be s traightforward. But one should carefully select the data structure to represent the sets Si so that set insertion and set enumeration can be done quickly , but no excessive amount of space is used. The actual usefulness of this procedure will of course depend heavily on the front length of the invasion used, and on the actual sizes of the sets si to be cons tructed.

VI . THE GENERAL CSP

So far we have looked ooly at CSPs involving binary constraints. Can our procedure also handle general CSPs with constraints involving more than two variables? The changes and generalisations necessary to answer this question positively should be obvious: we only need to generalize the notion of a constraint graph; variables correspond again to vertices, and two vertices are adjacent if the corresp::oding two variables are involved in some common constraint. With this definition of a constraint graph only a few modifications in bookkeeping are required so that the invasion procedure can be applied to general CSPs.

VII. FINDII'l:i A GOOD INVASIOO

In order to make efficient use of the algorithm of the last section, one needs "good" invasions, that is invasions with small front length. But good invasions do not exist for all graphs. Consider a complete n-vertex graph: each of its invasions has front length n-1. Furthermore there are n! invasions for an n-vertex graph, but no good algorithm is koown to select an optimal or almost ootimal invasioo. But if we restrict our attentioo to the class of planar graphs, we can exhibit an algorithm which oamputes an invasion with front length 0(/0). Similar algorithms exist for the classes of graphs of fixed genus. But we will concentrate on planar graphs. The importance of this class is illustrated by the fact that for instance most CSPs arising in A.I. vision involve planar constraint graphs.

In the construction of the invasion of a planar graph we will make use of a planar separator theorem by Lipton and Tarjan f7) :

Let G be an n-vertex planar graph. The vertices of G can be partitioned into three sets A, B, C, such that no edge joins a vertex in A with a vertex in B , neither A nor B contains more than 2n/3 vertices, and c contains no more than ran

vertices.

Lipton and Tarjan also exhibit an algorithm which finds such a partition in O(n) time. In [8] they shCJN how this theorem can be extended to graphs of arbitrary genus.

In the previous section we formally defined an invasion of a graph as a sequence of induced subgraphs. It should be clear that each invasion of a graph G induces a numbering on the vertices of G, and vice versa. Thus if the vertices of G are numbered XJ , .·. ,Xn, then (Gil G1 is the subgraph of G induced by the vertices Xi, with ~i}, i=l 1 ··· ,n, is clearly an invasion of G. So find1ng an invasion for a graph is equivalent to finding the corresponding numbering of its vertices.

In the folla,..ring we specify a divide and conquer type procedure INVADE-PLANAR-GRAPH which numbers the vertices of a planar graph. We shall mean by "invade S starting with i", where S is a subset of the n vertices of a graph and i an integer, l<i<n, that each integer between i and i + 1 s 1-1 is assigned to one of the vertices in s.

INVADE-Pil\NAR-GRAPH (G, l)

where INVADE-PLANAR-GRAPH (G,i) is:

• If there are no more than 4 vertices in G, invade them starting with i.

Otherwise, using Lipton's and Tarjan's method, partition the vertices of G into three sets A, B, C, such that there are no edges between vertices in A and vertices in B.

Invade C starting with i.

INVADE-PLANAR-GRAPH (GA,i+ICI).

INVADE-Pil\NAR-GRAPH <Gs , i + c +I A I ) ·

(GA ard Gs are the sul:x]raphs induced by A ard B respectively.)

Claim:

Given a planar n-vertex graph G, the above procedure yields an invasion for G whose front length f is smaller than 16*10.

Proof:

Let {Gi-l, i=l, ..· ,n, be the invasion irduced by the numbering of the vertices achieved by the above procedure. Let fi denote the front length of Gi for all i. Let A, B, C be the three sets into which the vertices of G are partitioned.

For all i , I C I < i ~ I C I+ I A I , f i llllSt be less than ICI+fb, where fA denotes the front length of the invasion of the sul:x]raph irduced by A.

For all i ~ ICI, fi llllSt be less than ICI ~ ran.

For all i, ICI+IAI < i ~ n, f llllSt be less than ICI+f& (with f 8 defined as fA), ~ause there are no edges between vertices in A and B and thus all the vertices in A must be conquered. Thus the following inequality holds:

Using the fact that neither A nor B contains more than 2n/3 vertices, we can derive the following recursive relation for the front length:

It can easily be shown that f(n) is bounded from above by c/ n, where c is not greater than 16. Thus the front length f is smaller that 16*/n. Q.E.D.

This result leads immediately to the following Corollary:

A CSP with n variables, m constraints, k values for each variable, and a planar constraint graph can be solved in time O(m*kl+l&fn) and space O(n*kl+l&rn).

VIII. COOCLUSION

We have described new algorithms to decide satisfiability, or to compute the complete set of solutions of a given CSP. The worst case complexities of the algorithms deperd heavily on the structure of the constraint graph of the CSP, so we do not claim that our method will be efficient for all CSPs. But we CXXIld shari that for CSPs with planar constraint graphs this algorithm leads to a considerable improvement in the asymptotic worst case complexity of the problem. It remains to be seen hari the proposed algorithms will behave in practical applications.

I would like to thank Alan Mackworth for bringing this problem to my attention. I also want to thank Alan, as well as David Kirkpatrick and Derek Corneil for helpful discussions and valuable CXXTrnents. Finally I want to thank an anonymous referee who pointed out the relation between the invasion method and standard backtrack search.