On a generalization of triangulated graphs for domains decomposition of CSPs

1 Introduction

Constraint-satisfaction problems (CSPs) involve the assign­ ment of values to variables which are subject to a set of con­ straints. Examples of CSPs are map coloring, conjunctive queries in a relational databases, line drawings understand­ ing, pattern matching in production rules systems, combina­ torial puzzles ... CSP is known to be a NP-complete problem. So, during last twenty years, many works have been proposed to optimize the classical Backtrack procedure, as constraint propagation, intelligent backtracking or network decomposi­ tions.

In [Jegou, 1993], another approach has been proposed which is based on the decomposition of the "micro-structure" of the CSP. The micro-structure of a CSP is the graph defined Philippe Jegou and Lamia Keddar LSIS- UMR CNRS 6168 Universite d' Aix-Marseille III Avenue Escadrille Normandie-Niemen 13397 Marseille cedex 20, France

*This work has been supported in part by the JUT de Lens, the CNRS and the Region Nord/Pas-de-Calais under the TACT Pro­ gramme

{philippe.jegou, lamia.keddar }@univ.u-3mrs.fr

by the compatible relations between variable-value pairs: ver­ tices are these pairs, and edges are defined by pairs of com­ patible vertices. Given the micro-structure of a CSP and us­ ing graph properties, the method realizes a pre-processing to simplify the problem with a decomposition of the domains of variables. For a CSP P, the decomposition generates a col­ lection of subproblems P1 , P2 , ... Pk. which is equivalent to the initial problem P . Each subproblem Pi has the size of its domains less or equal to the size of domains ofP, so the time complexity of each Pi is necessarily less than for the initial CSP. Moreover, given this collection of subproblems, we can separately solve them, or recursively apply again the decomposition.

This decomposition allows to transform an instance ofCSP in a collection of subproblems the domains size of which is less than domains size of the CSP. So, these sub-problems are theoretically easier to solve. Moreover, this decomposition defines and then gives a natural and efficient way for a paral­ lel implementation to solve CSP. In [Habbas eta!., 2000], an experimental analysis of this approach is presented, realized on a parallel configuration. These experiments show clearly the efficiency of the approach: the decomposition generally offers better results than the results obtained to solving the problems without decomposition. This advantage is related to the natural parallelization of the approach since each sub­ problem is solved independently. This fact is clear for consis­ tent CSPs. Moreover, if we consider inconsistent CSPs, the results are more insteresting: without parallelization, solving the problem after its decomposition is clearly better as solv­ ing it without decomposition.

In this paper, we present a generalization of this approach. This approach is based on a generalization of triangulated graphs. This generalization allows to define the level of de­ composition which can be fixed by a graph parameter. The larger this parameter is, the more level of decomposition (that is the number of sub-problems) is. As a consequence, we can then define the level of decomposition, with respect to the power of the parallel configuration used.

To define this generalization, we exploit a generalization of triangulated graphs called CSGk graphs which has been in­ troduced in [ Chmeiss and Jegou, 1997]. This class of graphs possesses the same kind of properties as triangulated graphs do. The most important here is the fact that the CLIQUE problem has a polynomial time complexity on these graphs.

First experiments reported here show that this extension increases significantly the advantage of the basic decompo­ sition, already shown in [Habbas eta/., 2000]. Indeed, we present experiments with two levels of decomposition. The basic decomposition, and the second level (CSG 2 graphs). The results show that for the second level of decomposition we obtain better results.

The section 2 recalls the decomposition method while sec­ tion 3 presents the generalization of the decomposition. Ex­ perimental results and a discussion about these result are pre­ sented in the section 4.

2 Preliminaries

2.1 Constraint Satisfaction Problems

A finite CSP (Constraint Satisfaction Problem) is defined as four tuple P = (X, D , C, R). X is a set of n variables x1, x2, ... Xn. D is a set of finite domains D1, D2, ... Dn, and C is a set of m constraints. Here we only consider binary CSPs, that is the constraints are defined on pairs of variables {Xi' X j} and will be denoted cij. To each constraint Cij' we associate a subset of the cartesian product ( Di x D j) which is denoted Rij and specifies which values of the variables are compatible with each other. R is the set of all Rij. A solution is an assignment of values to variables which satisfies all the constraints. For a CSP P, the pair (X, C) is a graph called the constraint graph. Given a CSP, the problem is either to know if there exists any solution, to find solution, or to find all solutions. The first problem is known be to NP-complete.

CSPs are normally solved by different versions of back­ track search. In this case, if d is the size of domains (maxi­ mum number of values in domains Di), the theoretical time complexity of search is then bounded by the size of the search space, that is dn. Consequently, many works tried to improve the search efficiency. At present time, it seems that the most efficient algorithm is the procedure MAC which has been in­ troduced in [Sabinand Freuder, I994] . Other approaches use decomposition techniques based on structural properties of the CSP. These methods exploit the fact that the tractability of CSPs is intimately connected to the topological structure of their underlying constraint graph. Moreover, these meth­ ods give an upper bound to the complexity of the problem. As example of such decompositions, we have tree-clustering scheme [Dechter and Pearl, 1989]. The time complexity of this method is bounded by dk where k is induced by the topo­ logical features of the constraint graph. Intuitively, more the constraint graph is dense, more the value k is large. For ex­ ample, if the constraint network is a complete graph, then k = n. So, the complexity of these decomposition methods is the same as for classical backtracking, that is dn. So, in [Jegou, 1993], Jegou proposed an alternative way to decom­ pose CSPs which is not based on the constraint graph but on the micro-structure of a CSP. In the sequel, we called this de­ composition scheme TR-Decomposition.

2.2 TR-Decomposition

Given a binary' CSP P = (X, D, C, R) such that (X, C) is a complete graph, p,(P) = (XD, CR) is called micro-structure ofP and it is an-partite graph where XD = {(xi , a) : Xi E X and a E Di} and CR = {{(xi, a), (xj, b)} : (a, b) E Rij }.

Note that if (X, C) is not a complete graph, for pairs of variables xi and x 1 such that the constraint Cij does not belong to set C, we consider the universal relation between these variables, that is Rij = Di x D1 (all pairs of values are compatible). The decomposition is based on a basic property of the micro-structure:

Theorem 1 Given a CSP P and its micro-structure p,(P), then (a1, ... an) E Solutions(P), that is (all ... an) is a solution of P, iff { (x1, a1), . .. (xn, an)} is a n-clique of p,(P) .

In other words, transforming a CSP as its micro-structure is clearly a polynomial reduction from CSP to CLIQUE, which is the problem of finding a clique of a given size belongs to a graph. As a consequence of this fact, as CSP, the CLIQUE problem is NP-Complete. Since the problem of finding an-clique is NP-hard, TR-Decomposition exploits the fact that triangulated graphs constitute a polynomial class of instances for this problem. We recall briefly basic properties of these graphs. Given a graph G = (V, E) and an ordering u = [v1 , . .. , vn] of V, the successors of a vertex Vi are the elements of the set N+(vi) = {v 1 E N(vi): i < j} where N(v) = {u E V : {u,v} E E}; a vertex Vi is simplicial in u if N+ (vi) is a clique. The ordering u = [v1 , ... , vn] of V is a perfect elimination ordering if, fori = 1, 2, ... n, the vertex vi is simplicial in the ordering u. A graph G = (V, E) is triangulated if and only if V admits a perfect elimination ordering. Triangulated graphs satisfies desirable properties. A triangulated graph on n vertices has at most n maximal cliques (a clique is maximal iff it is not included in an other clique) [Fulkerson and Gross, 1965]. Moreover, the problem of finding all maximal cliques in a triangulated graph is in O(n + m) if n is the number of vertices and m the number of egdes [ Gavril, 1972].

Given the micro-structure of any CSP, it is not possible to immediately use these properties because any micro-structure is not necessary a triangulated graph. So, in adding edges in E, we can build a new graph r(G) = (V, E') which is triangulated. This addition of edges is called triangulation, and can be realized in a linear time in the size of the graph. So, after the triangulation, all maximal cliques of G can be found in linear time. Applied to a CSP P = (X, D, C, R), the triangulation of its micro-structure p,(P) = (XD, CR) produces the graph f(p,(P) ), the set of maximal cliques of which is Y1 , ... Yk (k :S d.n). Every Y; is a set of values, and then defines a subproblem of P. More formaly, given a binary CSP P = (X, D, C, R), its micro-structure p,(P) = (XD, CR), andY a subset of XD. The CSP induced by Yon P, denoted P(Y) is defined by:

'Note that in [Hamadi, 1996], TR-Decomposition has been gen­ eralized to General CSPs, that is CSPs were constraints can be de­ fined on more than two variables.

• Dy = {DY,l, ... Dy,n} : DY,i = {a E D; : (x;, a) E Y}
• RY,ij ={(a, b) E Rij :(xi, a), (xj, b) E Y}
• P(Y) = (X,Dy ,C,Ry)

Finally, to ensure the validity of the decomposition, presents the theorem below:

Theorem 2 [Jegou, 1993] Given a binary CSP P, its micro-structure J.L(P) and {Y1 , .. . Yk}, the set of the maxi­ mal cliques off(JL(P)), then

Solutions(P) = u7=1 Solutions(P(Yi) ).

To summarize the approach, we recall the algorithm:

Algorithm: TR-Decomposition Begin

The steps 1, 2 and 3 can be realized in a linear time w.r.t. the size of the problem P. The procedure Triangulation re­ turns a perfect elimination ordering a which allows to the procedure Maxima/Cliques to find sets Yi- The step 4, that is the iteration for, can be replaced by a parallel execution on independent subproblems P(Yi). In this case, if the CSP P is consistent, the cost is related to the cost of solving the easiest subproblem, while it is the cost of the hardest sub­ problem for inconsistent CSPs. A such implementation has been realized in [Habbas eta!., 2000]. In step 5, a set Yi is not a covering of all the domains in D if there is a subdomain DY; ,j induced by Yi which is the empty set. This subproblem is then trivially inconsistent. In step 6, to solve P(Yi), we can use any classical search method such that standard backtrack­ ing, Forward-Checking or MAC [Sabin and Freuder, 1994]. Finally, note that the quality of decomposition depends on the quality of the triangulation step.

The last point is the most important. Nevertheless, it's well known that the problem of finding an optimal (w.r.t. the size of the largest induced clique) triangulation is NP-Hard (see [Amborg et al., 1987]). Several algorithms have been pro­ posed for triangulation. In all cases, the aim is to minimize either the number of added edges or the size of cliques in G'. Three classes of approaches are usable. The first one consists in finding an optimal triangulation which produces a graph the maximum size clique of which has minimum size over all triangulations. [Shoikhet and Geiger, 1997] propose a such algorithm the time complexity of which is exponen­ tial. The second is to find a minimal triangulation, that is a triangulation computing a set E1 such as if for any other triangulation E2 C E 1 the graph G' = (V, E U E2 ) is not triangulated. Note that a triangulation can be minimal and not optimal. See [Berry, 1999] who presents an algorithm in 0( n( n + m)). The last one consist in using a triangu­ lation consuming a linear time which does not gurantee the minimality. Nevertheless, the purpose of this paper is not to propose a good triangulation, but to exploit a generalization of triangulated graphs to generalize this decomposition. One of the aims of this generalization is to avoid the problem of finding optimal triangulations.

3 Generalizing TR-Decomposition

3.1 A first basic property

To generalize TR-Decomposition, we can extend the­ orem 2. Consider a CSP P = (X, D , C, R) and its micro-structure JL(P) = (XD, CR)· Consider a graph D..(J.L(P)) = (XD, 8(CR)) where CR ~ 8(CR). Consider now the set {Z1 , ... Z1} of maximal cliques of D..(J.L(P)). Every Zi is a set of values, and then, as in section 2.2, defines a subproblem of P which is the CSP induced by Z; on P (it is denoted P(Zi)).

Theorem 3 Given a binary CSP P, its micro-structure J.L(P) and { Z1 , .. . z1}, the set of the maximal cliques of D..(JL(P)), then Solutions(P) = u{= 1 Solutions(P(Zi)).

Proof. Given a binary CSP P, its micro-structure J.L(P) and by theorem 1, we know that each solution of P is a clique of size n. If we consider D..(JL(P)) = (XD, 8(CR)) where C R ~ 8 ( C R), each clique of J.L(P) is included in a maximal clique Z; of D..(JL(P)) . Therefore, each solution of P appears in the associated subproblem P(Zi)-

While TR-Decomposition is limited to triangulated graphs, theorem 3 allows to define a larger class of decomposition of domains. Nevertheless, because the number of maximal cliques can be exponential in an arbitrary graph, and then, the number of induced subproblems, we must consider graphs D..(J.L(P)) which possess a limited number of maximal cliques as triangulated graphs do. So, we exploit here a class of graphs which is a generalization of triangulated graphs.

3.2 A generalization of triangulated graphs

In [Chmeiss and Jegou, 1997], a new class of graphs, called CSGk graphs has been introduced. These graphs which generalize triangulated graphs, possess the same kind of properties as triangulated graphs, e.g. hereditary property of subgraphs, existence of an elimination scheme, polynomial time recognizing algorithm, and polynomial class of graph for CLIQUE problem. Informally, a CSG 0 graph is a complete graph, a CSG 1 graph is a triangulated graph, and a CSG 2 graph is a graph allowing an elimination vertex scheme where the successors of every vertex induce triangulated graphs. More generally, CSGk graphs are defined inductively.

Definition [ Chmeiss and Jegou, 1997] The class of CSG 0 Graphs is the class of complete graphs. Given k > 0, the class of CSGk graphs is the class of graphs G = (V, E) such that there exists an ordering a = [v1 , . .. , vn] of V such that fori= 1, 2, ... n, the graph G(N+(vi)) is a CSGk-l Graph. The ordering CJ is then called a CSGk scheme.

It's easy to see that CSG 1 Graphs is the class of trian­ gulated graphs. As for triangulated graphs, there exists a polynomial time algorithm R-CSGk for recognizing CSGk graphs; 'Vk:::: 2, its time complexity is O((n 2 )k- 1 (n + m)). In the context of decomposition of micro-structure, the num­ ber of maximal cliques is an important criteria. CSGk graphs inherit of a generalization of the property of Fulkerson and Gross [Fulkerson and Gross, 1965] related to this number since, a CSGk Graphs with n vertices have less than nk maximal cliques. Moreover, a CSG 2 graph with n vertices and m edges has at most n + m maximal cliques. Finding these cliques is easy, since, given a constant value k the CLIQUE problem is polynomial on this class of graphs since the time complexity of finding the clique of maximum size in an undirected CSGk graph is bounded by 0( n 2 (k-l) ( n+m) ).

3.3 TRk-Decomposition

CSGk graphs can be exploited as a way to generalizing ofTR­ Decomposition, defining IRk-Decomposition as decomposi­ tions corresponding to the class of associated graphs. Fork = 1, IRk-Decomposition is exactly TR-Decomposition, while fork = 2, IRk-Decomposition, that is TR 2 -Decomposition, it's the decomposition induced by CSG 2 graphs. More gen­ erally, IRk-Decomposition is summarized as:

Algorithm: TRk-Decomposition Begin

1 Build the micro-structure J..L(P) 2 k-Triangulation(J..L(P),~ k(J..L(P) ),CJ) 3 k-Maxima1Cliques(~k(J..L(P)),CJ,{Z1 , ... Zj}) 4 for all zi do 5 if Zi is a covering of all the domains in D 6 then Solve(P(Zi)) 7 else P(Zi) has no solution end for End;

Note that:

• The procedure k-Triangulation produces a graph ~k(J..L(P)) which is a CSGk graph and returns an order­ ing CJ which allows to the procedure k-Maxima/Cliques to find all the maximal cliques Zi of ~k(J..L(P)) .
• As for TR-Decomposition the step 4, that is the iteration for, can be replaced by a parallel execution on indepen­ dent subproblems P(Zi)· In this case, if the CSP P is consistent, the cost is related to the cost of solving the easiest subproblem, while it is the cost of the hardest subproblem for inconsistent CSPs.
• For steps 5 and 6, remarks given for TR-Decomposition hold.
• Finally, the quality of decomposition depends on the quality of the k-triangulation step.

Because of the time complexity of managing CSGk graphs, that is O(n 2 (k-l)(n + m)), it seems reasonable to focus our attention on small values of k. So, in the sequel we limit our study to CSG 2 graphs. Therefore, the number of maximal cliques will be bounded now by k ~ d.n + d 2 .n 2 . Nev­ ertheless, two problems must be adressed here. Finding an efficient algorithm for 2-triangulation, and an operational al­ gorithm to find maximal cliques of a CSG 2 graph.

For 2-triangulation, we can imagine an algorithm the time complexity of which is theoreticaly bounded by 0( nm( n + m)). This algorithm consider an ordering on vertices which is obtained by the Maximum Cardinality Search ofTarjan and Yannakakis. Given this ordering, we consider vertices vi, and then, we run a triangulation on G(N+(vi)) . This first step is in 0( n( n + m)) but this approach does not guarantee to get a 2-triangulation. Indeed, given two vertices vi and Vj, with i < j, the triangulation ofG(N+(vj)) which is realized af­ ter the triangulation of G ( N+ (vi)) can add edges that restore the new subgraph G ( N+ (Vi)) not triangulated. So, a second step of verification and repairing the subgraphs G ( N+ (Vi)) in adding new edges must be realized. This additionnal work induces a theoretical complexity ofO(nm(n + m)). Never­ theless, expermients show that this additionnal work will be rarely reached in practical cases (see section 4).

4 Experiments

Our aim in this section is to show the usefulness of the gener­ alized decomposition method comparing to the MAC (Main­ taining Arc Consistency) algorithm and the decomposition method by triangulation of the micro-structure and to give an idea about the efficiency of the proposed method. For the generalized decomposition method we will consider the TR 2 - Decomposition, i.e. k = 2.

As mentionned in section 3, we will not focus on the triangulation and 2-triangulation algorithms because it is not the principal objective of this paper. In experiments, we will use the Tarjan and Yannakakis's triangulation algorithm [Tarjan eta/., 1984]. This algorithm requires a precomputed elimination ordering on the vertices. Then, it adds edges, with respect to the ordering, which maintain the chordality property (i.e. when a vertex is treated, its successors must form a clique). Also, for the 2-triangulation, we will use an algorithm based on the Tarjan and Yannakakis's triangulation one as described in section 3.3. In practice, we have observed that the additionnal step is rarely realized and then the observed time of the 2-triagnluation is in n( n + m). So, for CSPs of great size, the CPU time used to decompose the problem is generally not significant with respect to the time of solving the CSP.

We have expermiented these methods on random CSPs generated at the phase transition. These CSPs are generated according to the model B generator [Prosser, 1996]. Such a generator admits four parameters:

• the number N of variables
• the common size of the initial domains D
• the proportion p 1 of constraints in the network (or the number C = p1 * N · (N- 1)/2 of constraints)

• the proportion p2 of forbidden pairs of values in a con­ straint (or the number T = p2 * D * D of forbidden pairs)

In the following, we will use C and T instead of p1 and p2. C is called the density of the constraint graph and T the tightness of the constraints. We have analysed decomposi­ tion using the procedure MAC as basic search algorithm (the used heuristic is dom/deg [Bessiere and Regin, 1996]). That is MAC has been used before decomposition on the initial problem and after decomposition on each induced subprob­ lem.

In order to have a credible idea on the performance of these methods, we consider several classes of problems. We vary two parameters (the number of variables Nand the domains size D). In order to deal with classes near the phase transition, we search the appropriate values of the tightness (T) and the density (C).

For each value of N, we vary D from small domains size to larger ones. So, we can observe the behavior of the de­ composition when D grows. Also, we have remarked that the performance of the decomposition method was not the same for satisfiable and unsatisfiable problems. So, we have chosen to present the results seperately.

Results are reported in three tables. Each table represents results for a given number of variables N. As measures of comparison, we used the number of consistency checks (#checks) performed by each of the methods and the number of visited nodes (#nodes). We mention that, the execution time is proportional to the number of checks.

In the tables, results are organized as following : the first column contains the calsses of problems represented by the four parameters < N, D, T, C >. For each class, we give results of the differents methods for satisfiable (Sat) and un­ satisfiable (Unsat) problems seperately. So, we have two lines per class. The second and the third columns give the number of subproblems induced by the TR-Decomposition and the TR 2 -Decomposition respectively. The fourth column indicates the number of satisfiable and unsatisfiable prob­ lems over the 50 randomly generated CSPs. The next three columns give the number of consistency checks for MAC, TR-Decomposition and the TR 2 -Decomposition respectively. The last three columns present the number of visited nodes by the different methods.

As the subproblems induced by the decomposition are in­ dependent, we can envisage a parallel implementation. In other words, we can imagine one process by subproblem. So, for saisfiable problems we consider the faster subproblem (the firstly solved subproblem since we have the response the it is satisfiable) while we consider the hardest subproblem for unsatisfiable ones.

Tables show, that decomposition improve the MAC algo­ rithm on all classes. The improvement is more significant for larger domains. Also, the performance of MAC is im­ proved more significately for denser constraint graphs. If we look at table 1 where N = 20, we remark that the TR 2 -Decomposition is five times faster than MAC for the < 20, 10, 30, 130 >. For classes with D = 20 the improve­ ment is more significant. This remark is confirmed when the constraint graphe is denser. For example, for the class < 20, 20, 130, 150 > and for satisfiable problems, the perfor­ mance ratio between TR 2 -Decomposition and MAC is about 1 to 22. In other words, for each consistency check performed by TR 2 -Decomposition 1' algorithm MAC performs 22 checks for satisfiable problems. For unsatisfiable problems, the per­ formance ratio is about 1 to 12.

This overall view on experiments shows that the general­ ized decomposition method is promising and results are en­ couraging. Finally, we would like to mention the importance of the triangulation (2-triangulation) phase. We think that the efficieny of the decomposition method is related to the quality of the triangulation (2-triangulation). We believe that other triangulation algorithms might offer a better decomposition.

5 Conclusion

In this paper, we have presented a generalization of the de­ composition of micro-structure, introduced in [Jegou, 1993]. This decomposition allows to transform an instance ofCSP in a collection of sub-problems easier to solve, and then gives a natural and efficient way for a parallel implementation [Hab­ bas et al., 2000]. While the original method is based on tri­ angulated graphs, our generalization is based on a generaliza­ tion of triangulated graphs called C SGk graphs. For a given value k, we get a special sub-class of graphs. E.g. CSG 0 graphs are complete graphs and CSG 1 graphs are triangu­ lated graphs. The value k allows to define a particular level of decomposition. So, we have introduced TRk-Decomposition as the generalized decomposition based on C SGk graphs.

There are two motivations for this generalization of the de­ composition:

• to extend the level of decomposition,
• to be able to fix this level to give an optimal exploitation for the parallel configuration used.

Indeed, it has been experimentally observed in [Habbas et al., 2000] that the first level of decomposition, that is TR 1 - Decomposition, outperforms classical algorithms, and that the more the number of sub-problems is, the more the effi­ ciency ofTR 1 -Decomposition is.

Our experimental results confirm these facts. We have studied two levels of decomposition, for k = 1 and k = 2 and the experiments show that TR 2 -Decomposition outperforms TR 1 -Decomposition. Moreover, the number of sub-problems is greater for k = 2 than for k = 1.

We have limited our experiments to k = 2 because the time complexity of managing CSGk graphs is related to the value k. More precisely, O(n2(k-l)(n+m)) is the time complexity to recognize these graphs. So in future works, we will try to propose efficient algorithms to realize decomposition.