A Comparison of Structural CSP Decomposition Methods

1 Constraint Satisfaction Problems

An instance of a constraint satisfaction problem (CSP) (also constraint network) is a triple I = (Var, U, C), where V ar is a finite set of variables, U is a finite do­ main of values, and c = {CI , c2, ... , Cq} is a finite set of constraints. Each constraint C; is a pair (S;,r;), where S; is a list of variables of length m; called the constraint scope, and r; is an m;-ary relation over U, called the constraint relation. (The tuples of r; indicate the al­ lowed combinations of simultaneous values for the vari­ ables S;) . A solution to a CSP instance is a substitution {): Var --t U, such that for each 1:::; i:::; q, S;{) E ri. The problem of deciding whether a CSP instance has any solution is called constraint satisfiability (CS). (This definition is taken almost verbatim from [Jeavons et al., 1997].)

Many problems in Computer Science and Mathemat­ ics can be formulated as CSPs. For example, the famous problem of graph three-colorability (3COL), is elegantly formulated as a CSP. Constraint Satisfiability is an NP­ complete problem.

It is well-known [Bibel, 1988; Gyssens et al., 1994; Dechter, 1992] that the CS problem is equivalent to vari­ ous database problems, e.g., to the problem of evaluating Boolean conjunctive queries over a relational database [Maier, 1986], or to the equivalent problem of evaluating join dependencies on a given database.

Francesco Scarc~llo ISI-CNR Via P. Bucci 41/C I-87030 Rende, Italy scarcello@si. de is. unical. it

This paper is organized as follows. In Section 2 we dis­ cuss tractability of CSPs due to restricted struCture. In Section 3 we briefly review well-known CSP decomposi­ tion methods. In Section 4 we describe the new method of hypertree decompositions. In Section 5 we explain our comparison criteria and in Section 6 we present the com­ parison results for general CSPs. The case of binary CSPs is briefly discussed in Section 7.

2 Tractable classes of CSPs

Much effort has been spent by both the AI and the database communities to indentify tractable classes of CSPs. Both communities have obtained deep and use­ ful results in this direction. The various successful ap­ proaches to obtain tractable CSP classes can be divided into two main groups [Pearson and Jeavons, 1997]:

1. Tractability due to restricted structure. This includes all tractable classes of CSPs that are iden­ tified solely on the base of the structure of the con­ straint scopes { S1 , ... Sq}, independently of the actual constraint relations r 1 , . .. , r q.

2. Tractability due to restricted constraints. This includes all classes that are tractable due to particular properties of the constraint relations r 1 , .. . , r q.

The present paper deals with tractability due to re­ stricted structure. The structure of a CSP is best rep­ resented by its associated hypergraph and by the corre­ sponding primal graph, defined as follows.

To any CSP instance I = (Var, U, C) , we associate a hypergraph 1i1 = (V, H) , where V = V ar, and H = {var(S) I C = (S, r) E C}, where var(S) denotes the set of variables in the scope S of the constraint C. Since in this paper we always deal with hypergraphs cor­ responding to CSPs instances, the vertices of any hyper­ graph 1i = (V, H) can be viewed as the variables of some constraint satisfaction problem. Thus, we will often use the term variable as a synonym for vertex, when referring to elements of V.

Let 1{1 = (V, H) be the constraint hypergraph of a CSP instance I . The primal graph of I is a graph G = (V, E), having the same set of variables (vertices) as 1i1 and an edge connecting any pair of variables X, Y E V

such that {X, Y} ~ h for some hE H.

Note that if all constraints of a CSP are binary, then its associated hypergraph is identical to its primal graph.

The most basic and most fundamental structural prop­ erty considered in the context of CSPs (and conjunctive queries) is acyclicity. It was recognized independently in AI and in database theory that acyclic CSPs are polyno­ mially solvable. I is an acyclic CSP iff its primal graph G is chordal (i.e., any cycle of length greater than 3 has a chord) and the set of its maximal cliques coincide with edges(1l1) [Beeri et al., 1983-].

A join tree JT(1l) for a hypergraph 1l is a tree whose nodes are the edges of 1l such that whenever the same vertex X E V occurs in two edges A1 and A2 of 1l, then A1 and A2 are connected in JT(1l), and X occurs in each node on the unique path linking A1 and A2 in JT(1l).

Acyclic hypergraphs can be characterized in terms of join trees: . A hypergraph 1l is acyclic iff it has a join tree [Bernstein and Goodman, 1981; Beeri et al., 1983; Maier, 1986]. Acyclic CSP satisfiability is not only tractable but also highly parallelizable. In fact , this problem is complete for the low complexity class LOGCFL [Gottlob et al., 1998] .

Many CSPs arising in practice are not acyclic but are in some sense or another close to acyclic CSPs. In fact , the hypergraphs associated with many naturally arising CSPs contain either few cycles or small cycles, or can be transformed to acyclic CSPs by simple operations (such as, e.g., lumping together small groups of vertices). Consequently, CSP research in AI and in database the­ ory concentrated on identifying, defining, and studying suitable classes of nearly acyclic CSPs, or, equivalently, methods for decomposing cyclic CSPs into acyclic CSPs.

3 Decomposition Methods

In order to study and compare various decomposition methods, we find it useful to introduce a general formal framework for this notion.

For a hypergraph 1l = (V, H) , let edges(1l) = H. Moreover, for any set of edges H' ~ H, let var(H') = UhEH' h; and for the hypergraph 1{, let var(1l) = var(H). W.l.o.g., we assume that var(H) = V, i.e., every variable in V occurs in at least one edge of 1l, and hence, any hypergraph can be simply represented by the set of its edges. Moreover, we assume w .l.o.g. that all hy­ pergraphs under consideration are both connected, i.e., their primal graph consists of a single connected compo­ nent, and reduced, i.e., no hyperedge is contained in any other hyperedge. All our definitions and results easily extend to general hypergraphs.

Let 1/S be the set of all (reduced and connected) hy­ pergraphs. A decomposition method (short: DM) D as­ sociates to any hypergraph 1l E 1/S a parameter D­ width(1l), called the D-width of 1l.

The decomposition method D ensures that, for fixed k, every CSP instance I whose hypergraph 1l1 has D­ width ~ k is polynomially solvable, i.e., it is solvable in O(III 0 ( 1 )) time, where III denotes the size of I. For any k > 0, the k-tractable class C(D, k) of D is defined by C(D, k) = {1ll D-width(1l) ~ k}. Thus, C(D, k) collects the set of CSP instances which, for fixed k, are polynomially solvable by using the strategy D. Typ­ ically, the polynomial above depends on the parameter k. In particular, for each D there exists a function f such that, for each k, each instance IE C(D, k) can be trans­ formed in time O(III 0 (/(k))) into an equivalent acyclic CSP instance (from where it follows that all problems in C(D, k) are polynomially solvable).

Every DM D is complete w.r.t. 1/S, i.e., 1/S = Uk>l C(D, k). Note that, by our definitions, it holds that D-width(1l) = min{k 11l E C(D, k)}.

All major tractable classes based on restricted struc­ ture fit into this framework. In particular, we shall com­ pare the following decomposition methods:

• Biconnected Components (short: BICDMP) [Freuder, 1985] . Any graph G = (V, E) can be decom­ posed into a pair (T, x), where T is a tree, and the la­ beling function x associates to each vertex of T a bi­ connected component of G (a component which remains connected after any one-vertex removal). The bicon­ nected width of a hypergraph 1l, denoted by BICDMP­ width(1l), is the maximum number of vertices over the biconnected components of the primal graph of 1l.
• Cycle Cutset (short: CUTSET) [Dechter, 1992]. A cycle cutset of a hypergraph 1l is a set S ~ var(1l) such that the subhypergraph of 1l induced by var(1l) - S is acyclic. The CUTSET width of 1l is the minimum cardinality over all its possible cycle cutsets.
• Tree Clustering (short: TCLUSTER) [Dechter and Pearl, 1989]. The tree clustering method is based on a triangulation algorithm which transforms the primal graph G = (V, E) of any CSP instance I into a chordal graph G'. The maximal cliques of G' are then used to build the constraint scopes of an acyclic CSP I' equiv­ alent to I. The tree-clustering width (short: TCLUSTER width) of 1l1 is 1 if 1l1 is an acyclic hypergraph; oth­ erwise it is equal to the maximum cardinality over the cliques of the chordal graph G'.
• Treewidth (TREEWIDTH) [Robertson and Seymour, 1986]. We omit a formal definition of graph treewidth here. The TREEWIDTH of a hypergraph 1l is the treewidth of its primal graph plus one. As pointed out below, TREEWIDTH and TCLUSTER are two equivalent methods.
• Hinge Decompositions (short: HINGE) [Gyssens et al., 1994; Gyssens and Paredaens, 1984], Let 1l be a hypergraph, and let V ~ var(1l) be a set of variables and X, Y E var(1l). X is [V]-adjacent to Y if there exists an edge hE edges(1l) such that {X, Y} ~ (h- V). A [V]-path 1r from X toY is a sequence X= Xo, ... , Xe = y of variables such that: xi is [V]-adjacent to xi+l' for each i E [0 ... £-1]. A set W ~ var(1l) of variables is [V]-connected if VX, Y E W there is a [V]-path from X to Y. A [V ]-component is a maximal [V]-connected non-empty set of variables W ~ (var(1l)- V). For any

[V]-component C, let edges(C) = {hE edges(1i) I h n c i- 0}.

Let 1i E 1!S and let H be either edges(1i) or a proper subset of edges(1i) containing at least two edges. Let C1 , ... , Cm be the connected [var(H)]-components of 1i. Then, H is a hinge if, for i = 1, ... , m, there exists an edge hiE H such that var(edges(Ci)) n var(H)) ~ hi. A hinge is minimal if it does not contain any other hinge. (Our definition of hinge is equivalent to the original one in [Gyssens et al., 1994; Gyssens and Paredaens, 1984].)

A hinge-decomposition of1i is a tree T such that all the following conditions hold: (1) the vertices ofT are mini­ mal hinges of 1i; (2) each edge in edges(1i) is contained in at least one vertex of T; (3) two adjacent vertices A and B ofT share precisely one edge L E edges(1i); moreover, L consists exactly of the variables shared by A and B (i.e., L = var(A) n var(B)); (4) the variables of 1i shared by two vertices of T are entirely contained within each vertex on their connecting path in T.

The size (i.e., the cardinality) of the largest vertex of T is called the degree of cyclicity of 1i. This is precisely what we call here the HINGE width of 1i. It was shown in [Gyssens and Paredaens, 1984] that for any CSP instance I, the HINGE width of 1i1 is the cardinality of the largest minimal hinge of 1i1.

· Hinge Decomposition + Tree Clustering (short: HINGETCLUSTER) [Gyssens et al., 1994]. It has been shown [Gyssens et al., 1994) that the minimal hinges of a hypergraph can be further decomposed by means of the triangulation technique of the above-described tree-clustering method. This leads to the HINGETCLUSTER method. LetT= (N, E) be a hinge tree of a hypergraph 1i. For any hinge H E N, let w(H) be the minimum between the cardinality of H and the TCLUSTER width of the hypergraph (var(H), H). The HINGETCLUSTER width of Tis maxHEN{w(H)}. Define the HINGETCLUSTER width of 1i as the minimum HINGETCLUSTER width over all its hinge decompositions.

For each of the above decomposition methods D it was shown that for any fixed k, given a CSP instance I, de­ ciding whether a hypergraph 1i1 has D-width(1i1) :::; k is feasible in polynomial time and that solving CSPs whose associated hypergraph is of width :::; k can be done in polynomial time. In particular, D consists of two phases. Given a CSP instance I, the (k-bounded) D-width w of 1i1 along with a corresponding decompo­ sition is first computed. Exploiting this decomposition, I is then solved in time O(lllw+l log III) (for most meth­ ods this phase consists of the solution of an acyclic CSP instance equivalent to I).

The cost of the first phase is independent on the con­ straint relations of I; in fact, it is 0(11iiictk+c 2 ) , where l1i1 I is the size of the hypergraph 1i1, and c1 , c2 are two constants relative to the method D (0 :::; c1 , c2 :::; 3 for the methods above). Observe also that computing the D-width w of a hypergraph in general (i.e., without the bound w :::; k) is NP-hard for most methods; while it is polynomial for HINGE, and it is even linear for BICOMP.

Further interesting methods that do not explicitly gen­ eralize acyclic hypergraphs are based on a notion of width as used in [Freuder, 1982; 1985]. If c is a total order­ ing of the vertices of a graph G = (V, E), then the C­ width of G is defined by we( G) = maxvE v I { { v, w} E E s.t. w C v }I. The width of G is the minimum of all c-widths over all possible total orderings C of V. For each fixed constant k, it can be determined in polyno­ mial time whether a graph is of width k. [Freuder, 1982] observed that many naturally arising CSPs are of very low width. Note that bounded width in this sense is a structural property. The following theorem shows that bounded width alone does not entail tractability.

Theorem 3.1 Constraint solvability remains NP­ complete even if restricted to CSPs whose primal graph has width bounded by 4.

Proof. 3COL remains NP-complete even for graphs of degree 4 (cf. [Garey and Johnson, 1979]). Such graphs, however, have width :::; 4. The theorem follows by the well-known natural encoding of 3COL as a CSP. I

Freuder showed that a CSP of width k whose rela­ tions enjoy the property of k'-consistency, where k' > k, can be solved in a backtrack-free manner, and thus in polynomial time [Freuder, 1982; 1985).

[Dechter and Pearl, 1988) consequently introduce the notion of induced width w* which is - roughly - the smallest width k of any graph G' obtained by triangu­ lation methods from the primal graph G of a CSP such that G' ensures k + !-consistency. Graphs having in­ duced width :::; k can be also characterized as partial k-trees [Freuder, 1990) or, equivalently, as graphs having treewidth :::; k [Arnborg et al., 1991]. It follows that, for fixed k, checking whether w* :::; k is feasible in linear time [Bodlaender, 1997]. If w* is bounded by a constant, a CSP is solvable in polynomial time. The approach to CSPs based on w* is referred to as the w*-Tractability method [Dechter, 1992). Note that this method is im­ plicitly based on hypergraph acyclicity, given that the used triangulation methods enforce chordality of the re­ sulting graph G' and thus acyclicity of the correspond­ ing hypergraph. It was noted [Dechter and Pearl, 1989; Dechter, 1992] that, for any given CSP instance I, TCLUSTER-width(1iJ) = w* (1i1) + 1.

4 Hypertree Decompositions of CSPs

A new class of tractable conjunctive queries, which gen­ eralizes the class of acyclic queries, has been recently identified [Gottlob et al., 1999]. Deciding whether a given query belongs to this class is polynomial time fea­ sible and even highly parallelizable. In this section, we first generalize this notion to the wider framework of hy­ pergraphs, and then show how to employ this notion in order to define a new decomposition method we will refer to as HYPERTREE.

A hypertree for a hypergraph 1i is a triple (T, x, >.), where T = (N, E) is a rooted tree, and x and >. are labeling functions which associate to each vertex p E N

two sets x(p) ~ var(1l) and A(p) ~ edges(1l). If T' = (N',E') is a subtree ofT, we define x(T') = UvEN' x(v). We denote the set of vertices N ofT by vertices(T), and the root ofT by root(T). Moreover, for any p E N, Tp denotes the subtree of T rooted at p.

Definition 4.1 A hypertree decomposition of a hyper­ graph 1l is a hypertree (T, x, A) for 1l which satisfies all the following conditions:

1. for each edge h E edges(1l), there exists p E vertices(T) such that vnr(h) ~ x(p);
2. for each variable Y E var(1l), the set {p E vertices(T) I Y E x(p)} induces a (connected) sub­ tree ofT;
3. for each p E vertices(T), x(p) ~ var(A(p));
4. for each p E vertices(T), var(A(p))nx(Tp) ~ x(p).

A hypertree decomposition (T, x, A) of 1l is a complete decomposition of 1l if, for each edge hE edges(1l), there exists p E vertices(T) such that var(h) ~ x(p) and h E A(p).

The width of the hypertree decomposition (T, x, A) is maxpEvertices(T) IA(p)l. The HYPERTREE width hw(1l) of 1l is the minimum width over all its hypertree decompo­ sitions.

Intuitively, if 1l is a cyclic hypergraph, the x labeling selects the set of variables to be fixed in order to split the cycles and achieve acyclicity; A(p) "covers" the variables of x(p) by a set of edges.

Example 4.2 Consider the following constraint scopes:

Let 1l1 be their corresponding hypergraph. 1{1 is clearly cyclic, and thus hw(1lt) > 1 (as only acyclic hyper­ graphs have hypertree width 1). Figure 1 shows a (com­ plete) hypertree decomposition of 1{1 having width 2, hence hw(1lt) = 2.

It is easy to see that the acyclic CSPs are precisely the CSPs of hypertree width one.

We say that a CSP instance I has k-bounded hypertree-width if hw(1li) :::; k, where 1l1 is the hyper­ graph associated to I. From the results in [Gottlob et al., 1999], it follows that k-bounded hypertree-width is efficiently decidable, and that a hypertree decomposition of width k can be efficiently computed (if any).

We next show that any CSP instance I is effi­ ciently solvable, given a k-bounded complete hypertree­ decomposition HD of 1l1 . To this end, we define an acyclic CSP instance which is equivalent to I and whose size is polynomially bounded by the size of I.

For each vertex p of the decomposition HD, we define a new constraint scope whose associated constraint rela­ tion is the projection on x(p) of the join of the relations in A(p). This way, we obtain a join-tree JT of an acyclic hypergraph 1l'. 1l' corresponds to a new CSP instance I' over a set of constraint relations of size O(nk) , where n is the input size (i .e., n = III) and k is the width of the hypertree decomposition HD. By construction, I' is an acyclic CSP, and we can easily show that it is equivalent to the input CSP instance I . Thus, all the efficient techniques available for acyclic CSP instances can be employed for the evaluation of I', and hence of I.

Theorem 4.3 Given a CSP I and a k-width hypertree decomposition of 1{1, I is solvable in O(nk lognk) O(nk logn) time, where n is the size of I .

5 Comparison Criteria

For comparing decomposition methods we introduce the relations ~' 1>, and -+< defined as follows:

D1 -< D2, in words, D2 generalizes D1, if :JJ 2: 0 such that, 'rfk > 0, C(D1 ,k) ~ C(D2,k+<l). Thus D1 ~ D2 if every class of CSP instances which is tractable according to D1 is also tractable according to D2 .

D1 1> D2 ( D1 beats D2) if there exists an integer k such that Vm C(D1 , k) ~ C(D2, m) . To prove that D11>D2, it is sufficient to exhibit a class of hypergraphs contained in some C(D1 , k) but in no C(D2,j) for j 2: 0. Intu­ itively, D1 1> D2 means that at least on some class of CSP instances, D1 outperforms D2 .

D1 -+< D2 if D1 ~ D2 and D2 1> D1. In this case we say that D2 strongly generalizes D1 .

Mathematically, ~ is a preorder, i.e., it is reflexive, transitive but not antisymmetric. We say that D1 is ~­ equivalent to D2, denoted D1 = D2, if both D1 ~ D2 and D2 ~ D1 hold.

The decomposition methods D1 and D2 are strongly incomparable if both D1 1> D2 and D2 1> D1. Note that if D1 and D2 are strongly incomparable, then they are also incomparable w.r.t. the relations ~ and -+<.

6 Comparison Results

Figure 2 shows a representation of the hierarchy of DMs determined by the -+< relation. Each element of the hi­ erarchy represents a DM, apart from that containing Tree Clustering, w*, and Treewidth which are grouped together because they are ~-equivalent as easily follows from the observations in Section 3.

Theorem 6.1 For each pair D1 and D2 of decompo­ sitions methods represented in Figure 2, the following holds:

• There is a directed path from D 1 to D2 iff D1 -« D2, i.e., iff D2 strongly generalizes D1.
• D1 and D2 are not linked by any directed path iff they are strongly incomparable.

Hence, Fig. 2 gives a complete picture of the relation­ ships holding among the different methods.

Below we sketch a proof of Theorem 6.1. For space reasons, we report only succinct versions of selected proofs. Detailed proofs of all results are available in the full version of this paper [Gottlob et al., 1999b].

For any n > 1 and m > 0, let Circle(n, m) be the hypergraph having n edges { h1 , ... , hn} defined as follows :

• hi= {Xl, ... ,Xf',Xl+1 , .. . ,XJ+1 } V1 :S i :S n -1;
• hn = {X~, .. . ,x~,xt, ... ,xr}.

Form= 1, Circle(n, 1) is a graph consisting of a simple cycle with n edges (like a circle) . Note that, for any n > 1 and m > 0, Circle(n, m) has hypertree width 2; a 2-width hypertree decomposition of Circle(n,m) is shown in Figure 3. Thus, (Un>l,m>O{ Circle(n, m)}) <;;; C(HYPERTREE, 2)

Lemma 6.2 HINGE-« HYPERTREE.

Proof. (HIN�E~ HYPERTREE.) Given a hinge decompo­ sition T = (V, E) of 1-l , we build a hypertree decomposi­ t ion HD of 1-l having the same width as T. HD has the same tree shape as T; the labels of a vertex p of (the tree of) HD are .A(p) = H and x(p) = var(H) , where H is the hinge corresponding top in the hinge decomposition.

(HYPERTREE !> HINGE.) For any k > 0, C(HYPERTREE, 2) :J (Un>l { Circle(n, 1)}) ~ C(HINGE, k). Indeed, for any n > 1, the degree of cyclicity of Circle(n, 1) is n [Gyssens et al., 1994]. I

Lemma 6.3 TCLUSTER-« HYPERTREE.

Proof. (TCLUSTER~ HYPERTREE.) Let 1-l = (V, H) be a hypergraph, and (T, 1/J) be the result of the application of the tree-clustering method on 1-l , where T = (N, E) is a tree, and 'lj; : N -+ 2v is a labeling function which assigns to each vertex ofT a set of variables of 1-l . For any p E N, the set of variables 'lj;(p) corresponds to a maximal clique identified by the tree-clustering method.

From (T, 1/J), we define a complete hypertree decom­ position HD = (T, x, .A) having the same tree T as the output of the tree clustering method. The labelings x and .A are defined according to the following procedure.

1. for each pEN, set x(p) = 'lj;(p) and .A(p) = 0;
2. for each edge hE H, choose a vertex pEN s.t. h <;;; x(p), and add h to .A(p) (i.e., .A(p) := .A(p) u {h});
3. While there is a vertex p E N s.t. x(p) contains a variable X not covered by .A(p) (i.e., X E (x(p) - var( .A(p))) , proceed as follows. (A) Find a path 1r in T linking p to a vertex q EN s.t. (i) X E var( .A(q)) and, (ii) X ¢ var(.A(s)) for every vertex sin 1r- { q}. (B) Choose an edge hE .A(q) s.t. X E h. (C) Add h to both .A(s) and x(s), for every vertex s E (1r- { q}) (i.e., x(s) := x(s) u h, and .A(s) := .A(s) u {h} ).

We have that HD is a complete hypertree decompo­ sition of 1-l , and its HYPERTREE width is smaller than or equal to the TCLUSTER-width of 1-l.

(HYPERTREE !> TCLUSTER.) Let S = { Circle(3, m) I m > 1} . For any m > 1, the primal graph G of Circle( 3, m) is a clique of 3m variables. Thus, G does not need any tri­ angulation, because it is a chordal graph. The TCLUSTER­ width of Circle(3, m) is clearly 3m; while its hypertree width is 2. Hence, for any k > 0, S ~ C(TCLUSTER, k) , whereas S <;;; C(HYPERTREE, 2). I

Lemma 6.4 HINGE and TCLUSTER are strongly incom­ parable.

Proof. (HINGE !> TCLUSTER) . From the proof above, S = {Circle(3,m) I m > 1} ~ C(TCLUSTER,k), for any k > 0. However , S <;;; C(HINGE, 3) , because every hyper­ graph in S has only three (hyper)edges.

(TCLUSTER !> HINGE) . From the proof of Lemma 6.2, (Un>l { Circle(n, 1)}) ~ C(HINGE, k) , for any k > 0. However , (Un>l { Circle(n, 1)}) <;;; C(TCLUSTER, 3) , be­ cause all these graphs can be triangulated in a way that their maximal cliques have cardinality 3 at most . I

Interestingly, even the combination of TCLUSTER with HINGE is strongly generalized by the hypertree­ decomposition method.

Lemma 6.5 HINGETCLUSTER-+< HYPERTREE.

Proof. The proof of HIN�ETCLUSTER~ HYPERTREE is very similar to that of Lemma 6.3, except that the ,\ la­ belings must be initialized in a suitable way (instead of 0). To see that HYPERTREE C> HINGErcwsrEa, note that (Un>l ,m>O { Circle(n, m)}) ~ C(HINGETCLUSTER, k) holds for any k > 0; while, (Un>l ,m>O{ Circle(n, m)}) ~ C(HYPERTREE, 2). I

7 Binary CSPs

On binary constraint networks, where the constraints relations have arity two, the differences among the de­ composition strategies highlighted in Section 6 become less evident. Indeed, bounding the arities of the con­ straint relations, the k-tractable classes of some decom­ position strategies collapse. In particular, as shown in the full version of this paper [Gottlob et al. , 1999b], on binary constraints networks, TCLUSTER = HINGErcwsrER and HINGETCLUSTER = HYPERTREE hold. The relation­ ships among the other decomposition methods remain the same as for the general case (Fig. 2) .

To evidentiate the differences of the above decomposi­ tion strategies on the domain of binary CSPs, we can compare their respective widths. For each discussed decomposition method D, any CSP instance I is solv­ able in time O(lllwH log III), once the D-width w of 1{1 along with a corresponding decomposition have been computed, as noted in Section 3. Thus, the D-width is a measure of the efficiency of a decomposition method: the smaller the D-width of 1i1, the more efficient the application of strategy D to I.

Theorem 7.1

1. For every binary CSP instance I, TCLUSTER-width(1i1 ) = HINGETCLUSTER_width(1i1).
2. For every binary CSP instance I, HYPERTREE-width(1ii) ~ TCLUSTER-width(1ii).
3. For some CSP instance I, TCLUSTER-width(1ii) = 2·HYPERTREE-width(1iJ).

Acknowledgments

Research supported by FWF (Austrian Science Funds) under the project Z29-INF and by the CNR (Italian Na­ tional Research Council) , under grant n.203.15.07.