Path Consistency on Triangulated Constraint Graphs

1 Introduction

The constraint satisfaction paradigm allows for a natu­ ral formulation of a wide variety of practical problems. It consists of representing a problem as a set of vari­ ables taking their values in particular domains, subject to constraints which specify consistent value combina­ tions. Solving a CSP amounts to assigning to the vari­ ables values from their domains, so that all the con­ strai~ts are satisfied. Backtrack search is the principal mechanism for solving a CSP. It is commonly combined with local consistency techniques to limit the combina­ torial explosion. These techniques reduce the size of the search space by removing local inconsistencies.

· Authors are listed in alphabetical order.

Djamila Sam-Haroud

Artificial Intelligence Laboratory

Swiss Federal Institute of Technology 1015 Lausanne, Switzerland

haroud@lia.di.epfl.ch

This paper considers a particular form of local consis­ tency called path consistency (PC). The work presented

considers binary CSPs and builds on their classical con­ straint graph representation, where the vertices represent the variables and the edges represent the constraints be­ tween the variables.

A path P = (u, ... , vi, ... , w) in a constraint graph G is PC if for all pairs of values for (u, w) that sat­ isfy the constraint Cu,w in G one can find values. for the intermediate variables Vi so that all the constramts Cu,v,, . .. , Cv, ,vi+,, . .. , Cvk ,w in G along the path are sat­ isfied (see figure 1). A constraint graph is PC iff ~II paths in the graph are PC [Mackworth, 1977]. In th1s paper we make the distinction between enforcing PC on CSPs and on constraint graphs. A CSP is PC if the comple­ tion of its constraint graph is PC. A CSP will be said to be partially PC (PPC) if its constraint graph is PC.

In practice, we know how to enforce PC on complete graphs thanks to the following theorem:

Theorem 1 (Montanari, 1974) A network with a com­ plete graph is PC iff every path of length two is PC.

As a result, existing algorithms first complete sparse graphs by adding universal binary constraints, then en­ force PC on each path of length two. The algorithms with the best time complexity [Mohr and Henderson, 1986; Han and Lee, 1988] run in time O(n 3 d 3 ). n is the number of variables and d the maximum domain size.

Despite its relatively high computational complexity, PC on complete graphs has been shown to be a cen­ tral notion for certain classes of problems. In effect, it has been shown to be equivalent to global consis­ tency for convex binary problems. This means that if a binary convex CSP is PC, its solutions can be de­ rived backtrack-free. The PC property has also re­ ceived particular attention in the area of temporal rea­ soning [Schwalb and Dechter, 1997] where lower forms of consistency prove to be of less interest.

In this paper we show that Montanari's theorem ex­ tends to triangulated constraint graphs. Triangulated constraint graphs can be made PC by ensuring that ev­ ery path of length two is PC. In this case there is no need for additional constraints to be synthesized. This allows us to devise an algor~thm for making a CSP with a triangulated constraint graph PPC in time O(bed 3 ). 6 is the maximum degree of the graph and e is the num­ ber of edges in the graph. When the original constraint graph is not triangulated, we can triangulate it by adding universal edges. It is important to note that for sparse problems, the number of edges added by triangulation is much less than by completion.

Given an incomplete constraint graph, we then com­ pare the pruning capacity of PC depending on whether it is enforced on a triangulation or a completion of the graph. We prove that for convex problems, the pruning capacity of the two is identical on the common edges. This means that, in this case, the extra edges synthe­ sized for completion do not affect the labeling of the common edges. We also propose an algorithm for filling in these extra edges.

Finally, we present some experiments illustrating that significant gains in computational effort can be obtained using our algorithms. Furthermore it appears that there is little difference in the pruning capacity of PPC and PC for general non-convex CSPs with triangulated con­ straint graphs.

2 Background

In this paper, we consider binary CSPs (V, C, D) where V is the set {1 , ... , i, ... , n} of variables, D is the set { D1, ... , Di, . .. , Dn} of domains and variable i takes its value in domain Di. The variables of V are subject to a set of constraints C = { Ci,j I Ci,j represent the legal value combinations from Di x Dj}· We use the (0, 1) matrix representation of constraints proposed in [Mon­ tanari, 1974] and assume that Ci,j is always the trans­ position of Cj,i· Ci,j = Di x Dj is called a universal constraint. A constraint is connected row-convex (CRC) if after removing the empty rows from its matrix repre­ sentation it is row-convex and connected, i.e. all the 1 entries in a row are consecutive and two successive rows either intersect or are consecutive [Deville et al., 1997].

A CSP is strongly PC if in addition to PC it also is arc consistent (AC). A CSP is globally consistent if any par­ tial instantiation of a subset of variables can be extended to a solution without backtracking.

Let us now recall the necessary background from graph theory. An undirected graph G is triangulated if every cycle of length strictly greater than 3 possesses a chord, that is, an edge joining two non-consecutive vertices of the cycle. For. a graph G = (V, E), with JVI = n, an ordering [v1 , ... ,vi, ... ,vn] of Vis a bijection of {1, ... ,n} onto V. For each v in V, the adjacency set Adj ( v), is defined as {w E V I (v,w) E E}. A vertex vis sim­ plicial if Adj(v) is complete. Every triangulated graph has a simplicial vertex. A triangulated graph remains triangulated after removing a simplicial vertex and its incident edges from the graph. The order in which sim­ plicial vertices are successively removed is called a per­ fect elimination order. For a given perfect elimination order, we will USe the notation Si = { Vn-i+l, ... , Vn}, and Gi will denote the subgraph of G induced by Si. Fi = {vk E Adj(vn-i) I Vn-i < vk} where< is the prece­ dence relation of the given order. Observe that since the elimination order is perfect, the subgraph of G induced by Fi is complete.

The material cited below is taken from[Kjcerulff, 1990]. A perfect elimination order can be found in O(n+e) time using the maximum cardinality search algorithm. A non­ triangulated graph can always be transformed into a tri­ angulated one by adding edges. Finding a minimal trian­ gulation, where every edge is necessary for the graph to be triangulated can be done in O(n(e+ f)) time, where f is the number of added edges. This bound is improved on average by a procedure called recursive thinning which we use in this work.

3 PC on Triangulated Constraint Graphs

In this section we extend theorem 1 to triangulated graphs. We show the following result:

Theorem 2 A triangulated constraint graph G is PC iff every path of length 2 is PC.

Proof: Since G is triangulated, we can find a perfect elimination order which defines Si, Gi and Fi as dis­ cussed above. We demonstrate that G is PC by induc­ tion on i. Since every path of length 2 is PC, we know by construction that G3 is PC. Assuming that Gi is PC, we set out to prove that Gi+1 is PC. We do this by showing that any path P from u tow in Gi+1 is PC.

If P is in Gi then P is PC by assumption. So we need to consider two cases. Either 1) as illustrated on the left in figure 2, Vn-i is an endpoint of P , e.g. Vn-i = w or 2) P goes through Vn-i as shown on the right in figure 2.

Let us consider these two cases below:

1. This path is considered for PC only if there is a constraint Cu,vn-i. Let us show that one can find values for the intermediate variables so that all the constraints along a path P are satisfied. Let y be the variable that precedes Vn-i in P. So in addition to the constraint Cu,vn-i we also have a constraint Cy ,vn-i. Since G is triangulated, the graph induced by F; is complete. So there is a constraint Cu,y· Now in G every path of length 2 is PC, so for ev­ ery pair of values that satisfy Cu,vn-i we can find a value for v that satisfies Cu,y and Cy ,vn-i. The part P~,y of the path P between u and y is in G; and is therefore PC by assumption. So for the pair of values found for ( u, y) we know that we can find values for the intermediate variables on this path P~.y. Hence we are able to find a set of values for all the intermediate variables between u and Vn-i that satisfy the constraints along P.
2. If P goes through Vn-i then let y and z be the vari­ ables that respectively precede and follow Vn-i in the path P. Note that both y and z are inS;. Since there is a constraint Cy ,vn-i> a constraint Cvn -; ,z and that the graph induced by F; is complete, we know that there is a constraint Cy,z· Now consider the path P~ , y; P~,w that goes directly from y to z without passing through Vn-i· P~ ; P~ w is in G; and therefore by assumption PC. T'his means that for any pair of values for (u, w) we can find values for the intermediate variables so that all the con­ straints along P~, y; P~ ,w are satisfied. Since in G every path of length 2 is PC, we also know that for the pair of values found for (y, z) we can find a value for Vn-i that satisfies both Cy ,vn-i and Cvn-; ,z· By doing so we just have found a set values that satisfy all the constraints along the original path P. 0

4 From Triangulated to Completed Graphs

Given the result in the previous section, the question arises whether more pruning can be obtained by com­ pleting a triangulated graph. As demonstrated in sec­ tion 6 this may indeed occasionally occur. However, in this section we show that for the class of convex prob­ lems, no additional pruning is obtained by completing the graph. The notion of convexity we refer to is a broad one. It includes the conventional definition of convexity in continuous domains, as well as its CRC extension to the discrete case. This extended convexity property is closed under composition and intersection of constraints.

To show our result on convex problems we need the following lemma.

Lemma 1 If G = (V, E) is an incomplete triangulated graph, then one can add a missing edge ( u, w), with u, w E V so that

1. the graph G' = (V, E U { ( u, w)}) is triangulated and
2. the graph induced by X= {xI (u, x), (x, w) E E} is complete.

Proof: Since G is triangulated, it has a perfect elimi­ nation order defining S;, G; and F;. Let i be the small­ est index such that G; is complete. Consider a variable Vj E S; for which there is no edge ( Vn-i, Vj) in G. By taking ( u, w) = ( Vn-i, Vj) we now prove the two claims of the lemma.

1. Since G; is complete, there is an edge between Vj and every variable in F;. The graph induced by F; in G' = (V, E U { ( Vn-i, Vj)}) therefore remains com­ plete. As a result, the considered elimination order is also perfect for G'. Since a graph with a perfect elimination order is triangulated, G' is triangulated.
2. Let us first show that X = F;. Suppose it is not. In that case we necessarily have that a y. E X that precedes Vn-i for which (vn-i,y), (y,vj) E E. But then, since G is triangulated, there would also be an edge ( Vn-i, Vj) which contradicts our assumption. Finally, since X = F; and G is triangulated, we know that the graph induced by X is complete. 0

This lemma is illustrated in figure 3. In this case

S; = { V3, V4, Vs, V6, V7}, Vn-i = V2 and F; = { V3, V6, V7}. The variables of F; are colored gray. The construction would for example add the dashed edge (v2 , v5 ) which is currently missing.

Let us now turn to the main result of this section.

Theorem 3 For a convex CSP with a triangulated con­ straint graph G, strong PC on G is equivalent to strong PC on the completion of G.

By equivalent we mean that the relations computed for the constraints in G are identical.

Proof: Suppose we have a triangulated graph G = (V, E) that is strongly PC. We will add to G the miss­ ing edges one by one until the graph is complete. To prove the theorem, we show that the relations of the constraints can be computed from the existing ones so that each intermediate graph, including the completed graph, is strongly PC.

To add the edges, we use the construction proposed for the proof of lemma 1. At all times during the constraint addition process, the graph therefore remains triangu­ lated. After the addition of a single edge (vn-i, Vj) toG, we obtain G' = (V, E U { ( Vn-i, Vj)}). For this edge the new relation Cvn-i ,v 1 is computed as follows:

where l8l is the composition operator. For example, in figure 3, Cv 2 ,v 5 is obtained by intersecting the compo­ sitions obtained via the variables in Fi = { v3 , v6 , V7} . Cvn_,,v, is the universal relation when Fi = 0.

If after making G strongly PC the relations in G are empty, the construction above would, as desired, com­ pute the empty relations for the missing edges. In what follows we therefore assume that the relations in G after strong PC are not empty.

We now show that G' is PC. Since G' is triangulated, by theorem 2 it is sufficient to prove that every path of length 2 is PC. By assumption, paths of length 2 that do not go through Vn-i and Vj are PC. So let us con­ sider paths of length 2 that go through Vn-i and Vj. By lemma 1 and the construction used in its proof, we know that the set of intermediate variables on the rele­ vant paths is Fi and that Fi induces a complete sub graph of G. This situation is illustrated in figure 4, where the variables in Fi are colored gray. Note that by construc­ tion the graph A induced by {vn-i}UFi and the graph B induced by Fi U { Vj} are complete. We have to consider

two cases 1 . With Vk' E Fi, either 1) P = (vn-i,Vj,Vk') or 2) P = (vn-i,Vk',vj)· Let us consider each of these cases in turn.

1. If P = (vn-i, Vj, Vk') we need to prove that for every pair of values for (vn-i, Vk') that satisfies Cvn_,,v., we can find a value for Vj so that Cvn-i ,v,, as defined by (1), and Cv,,v., are satisfied.

A is complete, strongly path-consistent and convex, it is therefore also globally consistent [Sam-Haroud and Faltings, 1996]. So that for every pair of values that satisfy Cvn_,,v., we can find values for all the variables in Fi - { Vk'} so that all other edges in A are also satisfied (see figure 4). Similarly, since B is complete, strongly path-consistent and convex it is globally consistent. This means that for the above values of the variables in Fi, we can find a value for Vj so that all constraints in B are satisfied. For the considered values the constraint Cv, ,v., is therefore satisfied. For any pair of values for Cvn-i ,v., we are hence able to find values for the variables in (Fi- {vk'} )U{vj} so that all constraints in AUB are satisfied. For the values for ( Vn-i, Vj), the relations Cvn_, ,v. and Cv. ,v, participating in (1) are therefore satisfied by the values for the variables in Fi. The values for (vn-i,Vj) therefore satisfy Cvn _,,v,·

1 The reasoning is the same for the symmetrical cases.

1. If P = (vn-i,Vk',vj) the relation Cvn_,,v, of the new edge ensures by definition that for every pair of values in Cvn_,,v 1 we can find a value for Vk' so that the Cvn_,,v., and Cv., ,v 1 are verified.

We now show that G' is AC. When IFil ;::: 1, since G' is PC we know that for every value pair in Cvn-· ,v., or in Cv., ,v 1 we can find a value pair that satisfies Cvn -i ,v,. Since G is AC this means that for any support respec­ tively on Cvn_, ,v., or on Cv.,,v, we are able to find a support on Cvn_, ,v,. As a consequence G' is not only PC but also AC. When IFi l = 0, Cvn-i ,Vj = Dvn-i X Dv,. Since G is AC, G' will therefore be AC as well. D

Corollary 1 is a direct consequence of theorem 3.

Corollary 1 For convex problems, insolubility is de­ tected using PC by graph completion iff it is detected using PC by graph triangulation.

5 Algorithms

By theorem 2 we know that triangulated graphs can be made PC by enforcing that every path of length two is PC. For problems with a triangulated constraint graph we can therefore make the CSP PPC by a sim­ ple modification of existing PC algorithms 2 . The result­ ing algorithm is Algorithm 1. The procedure Related-

Triplets(q) returns all those triplets in which q partici­ pates and that correspond to actual triangles in G. The difference with a classical PC algorithm, referred to as PC in the rest of the paper, is that PC revises all pos­ sible triplets, not only those corresponding to triangles in G. To determine the complexity of this algorithm for discrete problems, consider the number of revisions that can be made based on each edge (vi , vi). Revisions based on Cv, ,v, will be made only when a pair of values is re­ moved. If d is the maximum domain size, then one can remove at most d 2 pairs from any relation. Each removal prompts revisions only of the 2 neighboring edges in each triangle. If bv. is the degree of variable Vk, a modifica­ tion of Cv v will prompt at most 2 min { bv, - 1, bv, - 1} revisions. 's~mming over all edges we find that at most

2 PPC is close to Schwalb and Dechter's PLPC algorithm from which it borrows the name. PLPC (Partial Loose PC) enforces a partial form of path consistency on disjunctive temporal CSPs. It only considers the paths of length two with at least two non-universal constraints.

revisions will be performed, where J is the maximum degree. This should be compared to the C!(n 3 d 2 ) r~vi­ sions performed by the classical PC algonthm. Usmg the results presented in [Chiba and Nishizeki, 1985], one may use the arboricity o: of G instead of J, resulting in a number of revisions O(o:ed 2 ). The same reference also presents upper bounds on o: both for general graphs and for specific types of graphs.

For the experiments below we report the number of re­ visions since this measure is independent of the specific techniques one might use for updating the relations. In practice one can for example use the techniques based on the principle of minimal support used in PC-6 [Chmeiss, 1996]. In this case at most O(ed 2 ) value pairs may be deleted in the relations. Per value pair at most O(Jd) supports may be visited leading to a time complexity of O(Jed 3 ). However, per value pair only O(?) support i~­ formation concerning the smallest supportmg element 1s stored resulting in a O(Jed 2 ) space complexity. In case of CRC constraints one can use the techniques described in [Deville et al., 1997] to obtain a time complexity of O(Jed 2 ) and a space complexity of O(J~d). .

The PPC algorithm makes CSPs w1th tnangulated constraint graphs PPC. CSPs whose constraint graph is not triangulated can be made PPC by triangulating the graph with universal constraints before running PPC. For convex problems PPC is equivalent to PC. If de­ sired the relations of the missing edges can be computed as pr~posed in the proof of theorem 3. This fill algorithm is shown in Algorithm 2 below.

The variables are assumed to be ordered according to a perfect elimination order. Observe that it is not required to update the sets Fi when G changes, since the order in which the edges are added to Gi does not matter.

Algorithm 2 computes at most n(n- 1)/2 relations. Since each relation is computed by intersecting at most 2J compositions, the number of revisions Algorithm 2 needs to perform is therefore O(Jn 2 ). For CRC con­ straints one can, as before, use the techniques described in [Deville et al., 1997] to perform the actual computa­ tions. In this case the missing relations can be filled in in time O(Jn 2 d 2 ).

6 Experiments

In this section, we report some preliminary experiments that compare the number of revision steps carried out by PC and PPC for three types of randomly generated prob­ lems. The convex case is illustrated by tests on linear continuous and CRC problems, the non-convex one by tests on randomly generated discrete problems. For the linear problems, the constraints generated are inequali­ ties. They are discretized similarly to what is described in the work of [Sam-Haroud and Faltings, 1996] and rep­ resented by (0, 1) matrices. The constraint graph of each generated instance is triangulated before running PPC. The domain size is 8 for all the types of problems. Each test is averaged over 25 instances.

Table 1 shows the comparison for different sizes of con­ straint graphs and a fixed density p. The density chosen (p = 0.1) corresponds to sparse graphs and illustrates the most favorable case for PPC. Table 2 compares PC and PPC for problems of fixed size (n = 20) and differ­ ent densities. Since PPC is of interest on sparse CSPs, we report the experiments on sparse graphs (p ::; 0.5). For higher densities, the number of revisions of PPC ap­ proaches that of PC. Note that PPC and PC are identical for complete graphs.

By theorem 3 for convex problems the relations com­ puted by PPC and PC on the common edges are iden­ tical. For non-convex problems, we also compare the pruning capacity of PPC to the one of PC. pis the ratio between the number of tuples removed by PPC over the number of tuples removed by PC on the common edges. For the tests conducted on random problems, insolubil­ ity detected by PC was also detected by PPC.

The tests reported for non-convex problems are gener­ ated in the phase transition [Grant and Smith, 1996] as this seems to best illustrate the difference of behavior be­ tween PPC and PC. Indeed, several hundreds of tests run out of the phase transition showed no difference of prun­ ing between PC and PPC on the common edges. Note that the randomly generated linear and CRC problem instances do not necessarily fall in the phase transition.

It is worth mentioning that despite the worst case com­ plexity of O(n(e +f)) for triangulation algorithms, the effective time devoted to triangulation is negligible com­ pared to the running time of PPC.

More experiments clearly need to be conducted for better stating the effectiveness of PPC. The preliminary results we report are however encouraging enough to warrant PPC being investigated as alternative to PC for sparse problems.

7 Conclusion

Path consistency is an important notion in constraint satisfaction. A new algorithm, called PPC, is proposed that makes triangulated constraint graphs PC. PC can thus be enforced on incomplete constraint graphs by tri­ angulating instead of completing them. When the prob­ lem is sparse, this spares a significant amount of work compared to the classical PC algorithm. We have also shown that for convex CSPs with triangulated constraint graphs, the PPC and PC algorithms will compute the same labeling on the common edges.

Excessive memory requirements of existing PC al­ gorithms limit their applicability [Chmeiss and Jegou, 1996] . Since on sparse graphs PPC has a lower space complexity than PC, PPC might prove to be a viable alternative when memory is a limiting factor.

For non-convex problems, PPC exhibits a good prun­ ing capacity compared to PC and can be computed much more efficiently than PC on sparse graphs. We therefore expect that it might be beneficial to interleave it with backtrack algorithms to search for solutions. This will be a topic of future research.

8 Acknowledgments

We would like to thank Jean-Charles Regin for point­ ing out the results on arboricity. Most of this work was performed at the Artificial Intelligence Laboratory of the Swiss Federal Institute of Technology in Lausanne where Christian Bliek was sponsored by the Swiss National Sci­ ence Foundation under project number 2000-52363.97 through the ERCIM Fellowship Program.