When Functional and Bijective Constraints Make a CSP Polynomial

1 Introduction

Improving search efficiency of Constraint Satisfaction Problems (CSPs) is one of the main goals of researchers in this domain . Their works can be classified into different approaches, like improving backtrack proce­ dure [Haralick and Elliot, 1980; Dechter and Pearl , 1988], or filtering methods (arc and path consisten­ cies in particular) [Montanari , 1974; Mackworth, 1977; Mohr and Henderson, 1986] . Another approach is to characterize polynomial classes; they rely on structure of problems [Freuder, 1978] (leading to the presentation of new methods of decomposition [Dechter and Pearl , 1987; Dechter and Pearl, 1989; Jegou , 1990]) or on the size of their domains [Dechter, 1990]. Few works have been done on the semantics of the relations; recently, Deville and Van Hentenryck studied monotonic and functional constraints [1991], Perlin [1992] factorable relations , and van Beek [1992] identified a class of problems for which the tasks of finding a solution or the corresponding min­ imal network can both be solved efficiently.

Yet , in real applications, constraints don't take on any form. In particular a kind of constraints is often used: functional ones (VLSI tests [Stallman and Suss­ man, 1977], peptide synthesis [Janssen et a/., 1990]) .

In this paper, we will study functional and bijective constraints (the relations defined by these constraints are respectively a function and a bijection) . We will fo­ cus on the properties of arc and path consistencies when applied to these constraints, presenting a class of poly­ nomial problems and a method of decomposition.

Section 2 presents definitions and preliminaries, sec­ tion 3 and 4 expose results on functional and bijective constraints.

2 Preliminaries

We first present some definitions and the conventions we take in this paper:

A binary CSP P is defined by (X, D, C, R), where:

• X is the set of the n variables X1 , .. . , X;, .. . , Xn ;
• D is the set of the n domains D1, ... , D;, . .. , Dn , where D; is the set of the possible values for X; , d;, dj, dk are values of D;, Dj, Dk, respectively, and d is the size of the largest domain;
• C is the set of the m constraints, where a constraint C;j between the variables X; and Xj is defined by its relation R;i;
• R is the set of the relations R;i, where R;j is a subset of the cartesian product D; x Di specifying which values of the variables are compatible with each other.

A consistent instantiation of a subset Y of the vari­ ables xk,, . . . , xk, is a tuple of values ( dk,, ... , dk,) such that any constraint included in Y is satisfied. A solution is a consistent instantiation of X.

A graph g = (X, C) called constraint graph can be associated to a binary CSP P , where the vertices of g represent the variables of P, and the arcs (or edges), the constraints.

For any constraint C;j , we assign to R;j ( d;, dj) the boolean value true if and only if ( d;, di) belongs to the relation R;j .

If X; and Xj are not linked, C;i is called a universal constraint; we then have R;j ( d;, dj) for any ( d;, di) of D; x Dj (R;j = D; x Dj ). Universal constraints do not appear in C.

In the following, we will suppose that a CSP is con­ nected (its constraint graph is connected); if not, it can be decomposed into independant problems.

A value dk E Dk is called a support in Dk of a valued; for the constraint C;k iff R;k(d;, dk); it is called a support in Dk of a tuple (d;, di) iff R;k(d; , dk) and Rj~:(dj, d~:). Representations of relations can be either tables or graphs (see Figure 1).

We now recall the standard definitions of arc and path consistencies [Mackworth, 1977]:

Definition 2.1 A domain D; of D is arc consistent iff Vd; E D;, V Xi such that C;i E C, 3di E Di such that R;j(d;,di) ·

Definition 2.2 A CSP P is arc consistent iff VD; ED, D; is arc consistent and D; # 0.

Definition 2.3 A pair of variables {X;, Xj} is path consistent iff

V(d; , dj) E R;j , VX~: E X , 3d~: E D~: such that R;~:(d;,d~:) and Rj~:(dj ,d~;).

Definition 2.4 A CSP P is path consistent iff V X;, Xj E X , {X;, Xj} is path consistent.

In other words, a CSP is arc consistent iff any value of any domain has at least one support for any constraint (and no domain is empty), and it is path consistent iff any tuple of any relation has at least one support in any domain. ·

More generally, a CSP is k-consistent if and only if any consistent instantiation of k - 1 variables may be extended into any other variable to produce a consistent instantiation of k variables. It is globally consistent if and only if it is k-consistent for any k from 1 ton. For binary problems, arc and path consistencies are respectively 2 and 3 consistencies.

A CSP P is not necessarily arc or path consistent; it can in this case be transformed into an equivalent problem pc (i.e. it has the same solutions) by sup­ pressing inconsistent values from the domains (arc con­ sistency) or inconsistent tuples from the relations (path consistency); pc is then called arc (path) consistent clo­ sure of this CSP P [Montanari , 1974; Mackworth, 1977; Mohr and Henderson, 1986]. Notice that achieving path consistency may modify the constraint graph structure: some constraints may be induced instead of universal constraints (see Figure 1).

Given a CSP, the question can be to find all solutions, or one solution, or to know if there exists a solution; this problem is known to be NP-complete. However, some polynomial classes have been exhibited, based upon the size of the domains [Dechter, 1990], or upon structural properties of the CSPs (width lower than the consis­ tency degree of the CSP [Freuder, 1978]). Studying these classes provides bounds to the search complexity, and de­ composition methods: cycle-cutset method [Dechter and Pearl, 1987], tree clustering [Dechter and Pearl , 1989], cyclic clustering [Jegou, 1990].

Our purpose in this paper is to characterize polyno­ mial classes, based upon the semantics of two kinds of constraints: functional and bijective constraints; we also present a decomposition method improving search effi­ ciency in problems containing functional or bijective con­ straints.

3 Functional constraints

Definition 3.1

Given two variables X; and Xj, we denote X; -+ Xj iff for all d; E D; there exists at most one dj E Dj such that R;j(d; , dj) -

If it exists, the value is then noted dj = f;j ( d;) .

A constraint C;j is functional iff X; -+ Xj or Xj -+ X;.

The meaning of functional constraints is the same as this of functional dependencies used in the field of rela­ tional databases [Ullman, 1982].

For instance, the constraint Z = Y 2 is functional, with y-+ z.

We can notice that for any functional constraint C;j, IR;jl ~d.

When all the constraints are functional, achieving arc consistency is easy: AC4, the algorithm proposed by Mohr and Henderson [1986], is linear in the size of the problem; as the size of any relation is here bounded by d, the complexity is then O(md).

In the following, we study a binary CSP P composed with the subset c, of all functional constraints, and the subset of the other ones (non functional), C 0 . If it only contains functional constraints (Co = 0), Pis then called functional.

Let Q = (X, C) be the constraint graph of P. C contains both directed arcs representing functional con­ straints, where an arc is directed from X; to Xj iff X; - Xj, and edges (undirected arcs) for non functional constraints.

We can notice that arc and path consistency keeps the functionality property to any constraint (achieving it only suppresses values from domains and tuples from relations): when achieving arc consistency and path con­ sistency on a CSP P =(X, D, C1 UC0 , R), we obtain the CSP pc =(X, De, CJ u C~, Rc) where C1 ~ CJ. How­ ever, even ifP is functional (Co= 0), pc isn't necessarily functional, because non functional constraints may be in­ duced while achieving path consistency. Though, we can exhibit a class of induced constraints that are functional : transitivity constraints; property 3.1 characterizes them more formally:

Property 3.1 Let P = (X, D, C, R) be a CSP, p c =

(X, Dc, cc, Rc) its arc and path consistent closure, and g = (X, C) and gc = (X, cc) their constraint graphs. For all X;' xk in X I if there exists in c a sequence of functional constraints such that X; - Xk,, . . . , Xkj - xkj+I' ... 'xk. - Xk, then the constraint cjck of c c is functional (X;- Xk) ·

Proof:

Each constraint of the sequence is functional ; conse­ quently, it allows at most one dki+t for each dki .

The sequence of constraints C;, ... , Ck thus permits at most one dk for each d; .

The induced constraint C;ck is therefore functional : ~-~. D

This property is an immediate consequence of Armstrong's transitivity axiom for functional dependencies [Ullman, 1982].

We now recall some definitions issued from graph the­ ory and define notions used in the following of the sec­ tion.

Definitions 3.2 [Berge, 1970]

A variable Xj is a descendant from X; in a di­ rected graph (X, c,) iff there exists in c, a path (X;,Xk" ···,Xk. , Xi) such that X;- Xk"···,xk.­ Xi.

A variable Xr is a root of a directed graph (X , CJ) iff any other variable of X is a descendant from X r.

Definition 3.3

A subset n of variables of X is a root set of a direct ed graph (X, c,) iff any variable of X- n is a descendant from an element ofn.

Definition 3.4 Let g = (X, C1 ) .

An order on X is called r-compatible (with G or CJ) iff any variable Xj (except the first one) has at least one ancestor X ; in this order such that X ; - Xj .

Notice that the existence of such an order is equivalent to this of a root; any r-compatible order first element is a root.

Observe also a property of g c (Pc constraint graph): any order which is r-compatible with g is r-compatible with g c; moreover, any order which first element is a root (if it exists) is r-compatible with g c (see Figure 3) .

The results we present now rely on the following prop­ erty:

Property 3.2 Let P (X, D , C, R) be arc and path consistent, h-1 be a consistent instantiation of {Xt, .. . , Xk-d, and Xk a new variable to instantiate. If there exists Xi (1 ~ j ~ k- 1) such that Xi - Xk, then h-1 may be extended into a consistent instantiation of{Xt, ... ,Xk-t,Xk}.

Proof: Let h-1 = (dt, . .. , dk-I) be a consistent in­ stantiation of {Xt, . .. , Xk-d , Xk a new variable to be instantiated, and Xj an instantiated variable (1 ~ j ~ k- 1) such that Xi - Xk .

As P is arc consistent, there exists dk E Dk such that Rjk(dj , dk) (dk = fik(di)).

For all i < k

h -1 is consistent, so R;j ( d; , di);

P is path consistent, ( d;, dj) thus has a support in Dk : there exists d~ E Dk such that R;k(d;, dU and Rjk(dj, dU;

Xj - Xk , so there exists one only dk E Dk such that Rjk(dj,dk) (dk = /jk(dj)) ;

Consequently, d~ = dk, so R;k(d;, dk)

For all i < k we therefore have R;k(d; , dk) , which im­ plies that h = (dt , ... , dk-l, dk) is consistent . The instantiation may thus be extended to Xk. D

An interesting point in this property is that the condition only concerns the functional constraints; the num­ ber, the kind and the structure of the other ones don 't matter .

1 This is just an exemple of how achieving arc and path consistency may modify the constraint graph: the constraint C3s might as well have been induced.

The existence of an r-compatible order makes it more easy to solve the problem, as corollary 3.3 shows:

Corollary 3.3 Let P = (X, D, C, R) be arc and path consistent. If there exists on X an r-compatible order, then a solution exists and it can be found in linear time.

Proof: The instantiation order just has to be rcompatible.

As the instantiation order is r-compatible, any variable to be instantiated Xj owns at least one predecessor X; (thus X; is already instantiated with the valued;) such that X;--+ Xj. Due to property 3.2, dj = /;j(d;) may therefore instantiate Xj consistently. D

But such an order doesn't always exist; the problem can though be simplified due to the following corollary:

Corollary 3.4 Let P = (X, D, C, R) be arc and path consistent, and h-1 be a consistent instantiation of X1, ... , Xk-1·

If any non instantiated variable X; ( k ~ i ~ n) is such that there exists Xj verifying Xj --+ X; and 1 ~ j < k (there exists an instantiated variable Xj such that Xj --+ X;), then h-1 can be extended to a solution without backtrack.

Proof: Obviously deduced from property 3.2.

D

Notice that the properties of the set {X1, ... , Xk-d are these of a root set of G (see Figure 4) .

We can therefore deduce theorem 1:

Theorem 1 Let P = (X, D, C, R) be arc and path con­

sistent, and R ~X a root set of g =(X, C1 ).

If there exists a consistent instantiation ofR, then it can be extended to a solution without backtrack.

Proof: it's a direct consequency of corollary 3.4. D

An arc and path consistent problem is thus reduced into the resolution of one of its root sets; after this root set is consistently instantiated, this instantiation can be extended to a backtrack free solution. We can there­ fore deduce the number of solutions of the problem, as property 3.5 shows:

Property 3.5 Let P = (X, D, C, R) be arc and path consistent, and R ~X a root set of g = (X, CJ ).

The number of solutions of P equals the number of consistent instantiations of R: each consistent instan­ tiation of R can be extended to exactly one solution of P.

Proof: Let I = ( dk,, ... , dkJ be a consistent instantiation of R = Xk,, ... , Xkr.

Due to Theorem 1, I can be extended to at least one solution of P.

R is a root set of g; for all Xj E X - R there exists thus in R a variable Xk; such that Xk; --+ Xj. There is therefore an only dj in Dj such that Rk;j(dk; , dj) ·

For all Xj E X- R, there exists consequently at most one consistent instantiation of R U Xj containing I, and obviously at most one solution (containing/).

I can thus be extended to exactly one solution of P. D

As a solution can't obviously be an extension of two different instantiations of R, there is a bijection between the set of all consistent instantiations of R and the set S of the solutions of P.

A resolution method appears, that can be decomposed in four phases:

Phase 1: Determination of a minimum root set 2 R of g = (X,CJ) ·

Phase 2: Achievement of the arc and path consistent closure of P .

Phase 3: Instantiation of R.

Phase 4: Instantiation of X - R.

The phase 1 complexity is O(n + m) (determination of the strongly connected components [Tarjan, 1972]); phase 2 is 0( n 3 d 3 ) [Mohr and Henderson, 1986]; phase 3 needs O(dr) to instantiate R, where r is the size of R. At last, the instantiation of X - R is backtrack free; phase 4 can thus be achieved in 0( n - r) .

The complexity is so reduced from O(dn) for usual case, to O(n 3 d 3 + dr).

The size r of the root set is known from phase 1; the resolution complexity of a problem may consequently be bounded prior to the search.

As the problem can be reduced into its root set reso­ lution, a polynomial class appears, characterized by the following property:

Property 3.6 Let P = (X, D , C, R). If it owns a root set R which size is less or equal to 3, then it can be solved in O(n 3 d 3 ) .

Proof: The complexity is due to the computation ofPc, arc and path consistent closure of P.

If it fails , P admits no solution. Otherwise, as pc is arc and path consistent, up to 3 variables may be con­ sistently instantiated. As there are at most 3 variables in R, they just have to be instantiated first; after they are instantiated, corollary 3.4 guarantees we will find a solution without backtrack. D

Notice that a complete functional CSP P (X, D , C, R) ((X, C1) is a complete graph) owns at least one root: it can therefore be solved polynomialy. So, un­ like non functional CSPs, a complete graph offunctional constraints makes the problem more easy.

2 R ~ X is composed with one element from each source of the quotient graph obtained by reduction of the strongly connected components of g [David, 1992]

We will now study a subclass offunctional constraints: bijective constraints.

4 Bijective constraints

They are defined as follow:

Definition 4.1

A constraint C;i is bijective iff X; -+ Xi and Xi -+ X; .

If all its constraints are bijective, a CSP P is then called bijective. Otherwise, the set C of the constraints is divided into Cb and Co, respectively composed with the bijective constraints and the non bijective ones.

We now present definitions of an r-compatible order and a root set for bijective constraints:

Definition 4.2 Let G = (X, Cb).

An order on X is r-compatible iff any variable Xj except the first one owns at least one ancestor X; in this order such that C;i E Cb.

n is a root set of g iff for all X; of X I there exists Xr E n such that there exists a path from Xr to X; in cb.

Deville and Van Hentenryck [1991] presented some properties of arc consistency for bijective constraints 3 (in particular AC5, achieving arc consistency in 0( md)) ; our purpose is to extend these results to properties of path consistency.

First notice that bijective constraints are particular functional constraints. As such, they own all of their properties (in particular, the size of each relation is bounded by the size of the domain). But bijectivity is a stronger property than functionality, and we can expect this new class to own stronger properties, as property 4.7 shows:

Property 4.7 Let P = (X,D,Cb U Co,R) be a CSP, and pc = (X, De, c c, Rc) its arc and path consistent closure.

If g = (X, Cb) is connected, then p c is complete and bijective, and all domains D; have the same size.

Proof:

We first prove that p c is complete and bijective:

For any pair of variables {X; , Xj} ofP:

If C;j is a non bijective constraint of Co or an uni­ versal constraint:

cb is connected; there exists consequently a path J1- from X; to Xi in Cb, J1- = (X; = X; 0 ,X;,, ... ,X;,_,,X;, =Xi), such that Vp E [O .. k- 1], C;·;·+' is bijective.

As every C;·;·+' is bijective, there exists at most one dj allowed by this path for each d; (and in­ versely, at most one d; for each di ).

The constraint C~ computed by path consistency is therefore bijective.

If C;j is a bijective constraint, C;"i will also be bijec­ tive (achieving arc and path consistency only sup­ presses values from domains and tuples from rela­ tions) .

pc is thus complete and bijective.

3 they called them functional constraints

Let us now prove that all domains of p c have the same s1ze:

For any X;,Xj in X:

p c is complete and bijective, so cicj is bijective: any d; of D'j owns at most one support in DJ (and in­ versely, any di of DJ owns at most one support in Di) .

Moreover, as pc is the arc and path consistent clo­ sure of P , Cij is arc consistent: any d; of D'j there­ fore owns exactly one support in DJ (and inversely) : there is a one-to-one mapping between DJ and Di; their sizes are consequently equal.

All domains of pc thus have the same size.

D

In particular, the arc and path consistent closure of a bijective CSP remains bijective, unlike functional con­ straints where only the functionality of each constraint was kept. Moreover, as achieving arc and path consis­ tency on a CSP of which graph (X, Cb) is connected induces a complete graph of bijective constraints, any order on X is r-compatible.

We can now present the following property:

Property 4.8 Any bijective CSP that is arc and path consistent is globally consistent.

Proof: by induction on the degree of consistency. Let P = (X, D, C, R) be bijective, arc and path con­

sistent.

Suppose P is ( k - 1 )-consistent ; is it k-consistent?

Let Ik-1 = ( d1 , ... , dk~ 1) be a consistent instantia­

tion of {X1, ... , Xk-d·

The graph (X, C) is complete and bijective (prop­ erty 4.7), so any j verifies Xi -+ Xk)·

Due to property 3.2, h-1 can thus be consistently extended to X k.

Consequently, P is .k-consistent.

0

But the arc and path consistent closure of any P = (X, D, CbUC0 , R) isn't necessarily complete and bijective (if Cb isn't connected). The problem may though be decomposed, like functional constraints, with a root set ofP:

Theorem 2 Let P = (X, D, C, R) be arc and path con­ sistent, and R C X a root set of g = (X, Cb). If there exists a consistent instantiation of R, then it can be ex­ tended into a backtrack free solution.

Proof: like Theorem 1, with bijective constraints in­ stead of functional ones . 0

To build a minimum root set, we now just have to choose one (any) element in every connected component of (X, Cb)·

Moreover, as well as functional constraints, the num­ ber of solutions depends on the root set of 9:

Property 4.9 Let P = (X, D, C, R) be arc and path consistent, and R C X a root set of g = (X, Cb)· The number of solutions ofP equals the number of consistent instantiations of R .

Furthermore, if P is also bijective, there exist exactly de solutions, (where de is the size of each domain ofP ).

Proof:

The first part of the property is similar to property 3.5. IfP is bij ective , properties 4.8 and 4.7 respectively tell us that P is globally consistent (so any variable is a root set) , and that all domains have the same size de. The number of consistent instantiations of R is thus the size of any domain. 0

5 Conclusion

We presented in this paper some properties of arc and path consistencies for two classes of constraints, func­ tional and bijective constraints, and characterized poly­ nomial problems. We also proposed a decomposition method for these classes, based upon the semantics of the const raints . Yet, many works remain to be done about this subject; in particular , extending this work to non binary constraints, as well as studying other classes of constraints, like monotonic constraints for instance.

Acknowledgments

I wish to thank Philippe Janssen and Marie-Catherine Vilarem for their helpful comments.