Non-Binary Constraints and Optimal Dual-Graph Representations

1 Introduction and summary of results

Constraint satisfaction is a central issue of AI research and has an impressive spectrum of applications (see, e.g., [Pearson and Jeavons, 1997]). A constraint (S;, R;) con­ sists of a constraint scope S;, i.e., a list of variables and of an associated constraint relation r; containing the le­ gal combinations of values. A CSP consists of a set { (S1, rl), (S2, r2), . .. , (Sq, r q)} of constraints whose vari­ ables may overlap. A solution to a CSP is an assignment of values to all variables such that all constraints are simul­ taneously satisfied. By solving a CSP we mean determining whether the problem has a solution at all (i.e., checking for constraint satisfiability), and, if so, compute one solution.

Constraint satisfiability in its general form is well-known to be NP-hard. Much effort has been spent to identify tractable classes of CSPs, and deep and useful results have been achieved. The various successful approaches to ob­ tain tractable CSP classes can be divided into two main groups [Pearson and Jeavons, 1997]: the techniques that iden­ tify tractable classes of CSPs only on the base of the structure of the constraint scopes { S1 , ... Sq} independently of the actual constraint relations r 1 , ... , r q and the techniques that identify tractable classes by exploiting particular proper­ ties of the constraint relations r 1 , . .. , r q. In this paper, we will deal with this latter group of techniques, usually called structural decomposition methods. There are several papers proposing polynomially tractable classes of constraints based on different structural properties of constraint-scopes inter­ actions (see, e.g., [Dechter, 1992; Dechter and Pearl, 1989; Gyssens et al., 1994; Gottlob et al., 2000]). Such a structure is best represented by the hypergraph 1i(I) = (V, H) associ­ ated to any CSP instance I = ( Var, U, C), where V = Var and H = { var(S) I C = (S, r) E C}, and var(S) denotes the set of variables in the scope S of the constraint C. We often denote the set of vertices by N(1i) and the set of hy­ peredges by £(1i).

However, many interesting techniques for solving CSPs or for identifying tractable classes of CSPs have been de­ signed for binary CSPs, i.e., CSP instances where each scope contains two variables at most. Therefore, historically, the first attempts to deal with general (i.e., non-binary) constraint problems try to exploit the existent methods, by represent­ ing any CSP instance I by some graph, rather than by the hypergraph 1i(I). A first idea is to use the primal graph of 1i(I), whose edges connect each pair of variables occurring together in some constraint of I. Clearly, there is an evident loss of information in using the primal graph instead of the hypergraph. For instance, each constraint-scope of I induces a clique in the primal graph, but if one looks at the graph only, there is no way to understand whether such a clique comes from a hyperedge of the hypergraph, or by some in­ tricate interactions among scopes. In fact, in [Gottlob et al., 2000], a deep comparison among various structural decompo­ sition methods showed that some technique designed for hy­ pergraphs is more powerful than all the (known) techniques working on the primal graphs. In this paper, we focus on the other two important graph-based representations of non­ binary constraints, described in the literature, only marginally considered in that work:

Dual-graph Representation [Dechter, 1992]. Given a hy­ pergraph 1i, its dual graph, denoted by dual(1i) = (N, E), is the graph whose set of vertices N is the set of hyper­ edges £(1i), and whose edges connect each pair of vertices (i.e., hyperedges) having some variable in common, that is E = { {h1, h2} I h1, h2 E £(1i) and h1 n h2 i 0}

Hidden-variable Representation [Seidel, 1981; Chekuri and Rajaraman, 2000]. Given a hypergraph 1i, we define its incidence graph as the bipartite graph inc(1i) = (N, E), where N = £(11) U N(11), and E = { {h,a} I h E £(11) and a E h)}, i.e. it contains an edge from h to a if and only if a is a node of h. (E.g., Figure 2 shows a constraint hypergraph (a) and its incidence graph (b)).

There is a great interest in comparing CSP solving tech­ niques based on these encodings of the structure [Bacchus et al., 2002] and long standing questions about their relation­ ships with hypergraph-based techniques, described below.

One of the major difficulties in doing precise and formal analysis of dual-graph based methods is due to an impor­ tant feature of this encoding: some edges of the dual graph can be safely removed from this graph, making the evalua­ tion of CSPs easier. Indeed, even if dual(11) appears very intricate, sometimes is possible to find suitable simplifica­ tions that make it much more useful. Such simplified graphs are called reducts of dual(11). For instance, if 11 is acyclic, there is a polynomial time algorithm for making its dual graph acyclic, and in fact a join tree of 11. An example is shown in Figure 2.c, where the acyclic graph obtained by removing the dashed edges is a join tree of the given hypergraph. However, different removal choices may lead to different performances of evaluation algorithms. Thus, the efficiency of any tech­ nique based on the dual graph depends crucially on the avail­ ability of a good algorithm for simplifying the dual graph. Note that finding the "best reduct" is a difficult task and is currently not known whether it is feasible in polynomial time, in general.

On the other hand, the fact that effective dual graph rep­ resentations are not unique made comparisons among dif­ ferent methods quite difficult. For instance, Gyssens et al. [1994] compared the notion of Hinge decompositions (short: HINGE) and the notion of Biconnected components of the dual graph (short: BICOMPd). It turned out that HINGE is a generalization of BICOMPd, and thus the hinge decomposition technique is not worse than the biconnected components tech­ nique. However, the precise relationship between these meth­ ods remained an open question, because biconnected compo­ nents can perform very bad unless "clever simplifications" of the dual graph are chosen.

The first contribution of this paper is solving this question. First we formally define, for each method D, the method Doptd, that is, the method D applied to the best possible. simplification of the dual graph with respect to D. Indeed, in general, the notion of best simplification depends on the method D used for decomposing the graph. This way, meth­ ods applied to dual graph encodings are well-defined and can be compared with other methods.

We formally prove that BICOMPoptd is equivalent to HINGE. In fact, we show that any hinge decomposition corresponds to the biconnected-components tree of some reduct of the dual graph. It is worthwhile noting that, as a corollary of this result, we obtain that, for the BICOMPoptd method, an opti­ mal reduction of the dual graph can be computed in polyno­ mial time, since any hinge decomposition can be computed in polynomial time.

Then, we consider the powerful decomposition method for dealing with graphs: the tree decomposition method [Robert­ son and Seymour, 1986], which is equivalent to the tree­ clustering method [Dechter and Pearl, 1989]. It is known that any class of CSP instances such that the treewidth of their incidence graph (respectively, of some reduct of their dual graphs) is bounded by some constant k is tractable. That is, all such instances may be evaluated in time O(nc), where n is the size of a CSP instance and c is a constant that depends crucially on the bound k on the decomposition width.

We perform a detailed comparison of the tree decom­ position method applied to the incidence graph of the hy­ pergraph (i.e., on the hidden-variable encoding), denoted by TREEWIDTifn, and the tree decomposition method ap­ plied to some optimal reduct of the dual graph, denoted by TREEWIDTWptd. It turns out that every CSP class that is tractable according to TREEWIDTHin is tractable according to TREEWIDTHoptd, as well. Moreover, there are CSP classes that are tractable according to TREEWIDTWptd but are not tractable according to TREEWIDTifn, i.e., their largest width is not bounded by any fixed number. However, we show that TREEWIDTWptd does not strongly generalize TREEWIDTHin. Indeed, there are classes of CSPs whose incidence-graph treewidth is bounded by a constant k, but the largest width of some optimal reduct of the dual graph is much greater. Thus, even if such classes are tractable, their evaluation can be much more efficient by using the TREEWIDTifn method. It follows that either of these methods may be useful for some kind of CSP instances, and hence there is no definitely better choice between them.

Finally, we focus on further interesting open ques­ tions about TREEWIDTHoptd . Define the optimal treewidth twoptd(11) of the dual graph of some hypergraph 11. as the minimum treewidth over all reducts of dual(11.). Kolaitis and Vardi [2000] observed that is not trivial to find a "good" reduct of the dual graph and defined the following prob­ lem k-OPT, for any fixed constant k > 0: Given a hyper­ graph 11, decide whether the optimal treewidth of dual (11.) is at most k. The question is whether k-OPT is decidable in polynomial time or not, that is whether there is an effi­ cient way for computing a reduct of the dual graph that have the minimum treewidth. Moreover, even if it is · known that TREEWIDTWptd is strongly generalized by the hypertree de­ composition method [Gottlob et al., 2000), it is not clear why there is such a big difference between these methods. Indeed, at a first glance the kind of tree labelling in these methods seems rather similar.

We face both the above questions. Let k > 0 be a fixed constant and 11 be a constraint hypergraph. We present a polynomial time algorithm k-TREE-APPROX that, if the optimal treewidth of dual(11.) is at most k, out­ puts a tree decomposition of width at most 2k of some reduct of dual(11.). Thus, k-TREE-APPROX provides a 2-approximation of TREEWIDTHoptd. Note that the ques­ tion whether k-OPT is decidable in polynomial time remains open, because k-TREE-APPROX can compute a tree decom­ position of width at most 2k even if the optimal treewidth k' of dual(11.) is greater thank, i.e., if k < k' :::; 2k.

Moreover, our algorithm is also able to compute a new kind of structural decomposition that allows us to shed some light on the striking difference between TREEWIDTWptd and the more general hypergraph-based notions of query decomposi­ tion and hypertree decomposition.

2 Preliminaries

It is well known that CSPs with acyclic constraint hyper­ graphs are polynomially solvable [Dechter, 1992]. The known structural properties that lead to tractable CSP classes are all (explicitly or implicitly) based on some generaliza­ tion of acyclicity. In particular, each method D defines some concept of width which can be interpreted as a measure of cyclicity of the underlying constraint (hyper)graph such that, for each fixed width k, all CSPs of width bounded by k are solvable in polynomial time. This (possibly infinite) set of CSPs is called the tractability class of D w.r.t. k, and is de­ noted by C(D, k). Any pair of decomposition methods D1 and D2 can be compared according to their ability to iden­ tify tractable classes of CSPs. Formally, Gottlob et al. [2000] defined the following criteria:

Generalization. D2 generalizes D1 (D1 ~ D2) if there ex­ ists a constant o such that, for each k > 0, C(D1 , k) ~ C(D2, k + o). In practical terms, this means that when­ ever a class C of constraints is tractable according to ~ethod D1 , it is also tractable according to D2 .

Beatmg. D2 beats D1, denoted by D2 1> D1, if there exists an integer k > 0 such that C(D2 , k) is not contained in class C(D1,m) for any m > 0. Intuitively, this means that some classes of problems are tractable according to D2 but not according to D1. For such classes, using D2 is thus better than using D1 .

Strong generalization. D2 strongly generalizes D1 , de­ noted by D1 -+< D2, if D2 generalizes D1 and D2 beats D1. This means that D2 is really the more powerful method, given that, whenever D1 guarantees polynomial runtime for constraint solving, then also D2 guarantees tractable constraint solving, but there are classes of con­ straints that can be solved in polynomial time by using D2 but are not tractable according to D1.

Equivalence. D1 and D2 are equivalent, denoted by D1 :::: D2, if D1 generalizes D2 and D2 generalizes D1. Intu­ itively, this means that these two methods do not differ significantly from each other.

We assume the reader is familiar with the main structural decomposition methods proposed in the literature (see, e.g., [Pearson and Jeavons, 1997]). Anyway, for the sake of pre­ sentation, we recall the definition of graph treewidth.

A tree decomposition [Robertson and Seymour, 1986] of ~ graph G = (V, E) is a pair (T, x), where T = (N, F) IS a tree, and x is a labelling function associating to each vertex p E N a set of vertices x(p) ~ V, such that the following conditions are satisfied: (1) for each vertex b of G, there exists p E N such that b E x(p); (2) for each edge {b, d} E E, there exists p E N such that {b, d} ~ x(p); (3) for each vertex b of G, the set {p E N I b E x(p)} induces a (connected) subtree ofT. (Connectedness condition.)

The width of the tree decomposition (T, x) is maxpEN lx(p) - 11- The treewidth of G, tw(G), is the minimum width over all its tree decompositions.

We next formally define how the dual graph dual(1-l) of a hypergraph 1-l can be simplified, by removing edges in a suit­ able way. For any edge { h, h'} of a dual graph, let f( { h, h'}) denote the set of variables h n h' that the hyperedges h and h' have in common.

Definition 2.1 Let G = (V, E) be the dual graph of some hypergraph 1-l. A reduct G' of G is a graph (V', E') such that V' = V, E' ~ E, and the following condition holds: for each edge q = { h, h'} belonging to (E- E'), there exists in G' a path P from h to h', such that the variables in f(q) are included in f(q') for each edge q' occurring in the path P. That is, if all the variables shared by h and h' occur in some other path between these vertices, the edge connecting them can be deleted from the dual graph.

Let h be a hyperedge of 1-l, and G be a reduct of dual(1-l). !hen, we denote with va(h) the vertex of G' correspond­ mg to the hyperedge h. Moreover, given a set of hyperedges H, we denote by va(H) the set of vertices of G' associated with the elements in H. Whenever no confusion arises, va(h) (r.esp. va(H)) will be denoted simply by v(h) (resp. v(H)). Fmally, we denote by duala(H) the subgraph of G induced by the nodes in va(H).

A non-binary CSP can be solved by applying any binary decomposition method, say D, to any reduct of the dual graph. However, the performance of this method depends in general on the particular reduct selected for solving the prob­ lem. We are interested in the reduct that guarantees the best possible performances, when the method D is applied to it. Formally, given a hypergraph 1-l, define novtd as the method D applied to the reduct of dual(1-l) having the minimum D­ width over all the possible reducts of dual(1-l).

It can be seen that the strongly generalization results be­ tween graph-based decomposition methods proved by Gott­ lob et al. [2000] can be extended to their optd versions.

Theorem 2.2 The following relationships hold:

• BICDMPoptd -+< TREEWIDTHoptd.
• CUTSEToptd -+< TREEWIDTWptd.

Thus, TREEWIDTWptd seems a good candidate for solving non-binary CSP, as it strongly generalizes all the other graph­ based methods. However, we recall that all the known al­ gorithms for computing a k-bounded tree decomposition of a graph are exponential in k (even if they are polynomial for any fixed constant k), while computing the biconnected components of a graph is a linear task, independently of their width. This latter technique can be therefore very useful if the size of the structure and the bound k are large and the pow­ erfill methods like TREEWIDTH are too expensive. In the next section, we face the problem of computing optimal reducts of the dual graph w.r.t. the BICOMP method.

3 Hinges VS Biconnected Components

In [Gyssens et al., 1994], it has been shown that the HINGE method generalizes BICOMP applied to any reduct of the dual graph. Anyhow, in the same paper, Gyssens et al. observed that a fine comparison between the two methods is quite dif­ ficult, as there is no obvious way to find a suitable reduct of the dual graph to keep the biconnected width small. Here we complete the picture by showing that, in fact, hinge decom­ positions correspond to such clever simplifications of the dual graph.

Lemma 3.1 HIN�E~ BICOMPoptd.

Proof. (Sketch.) Let 1-l be a hypergraph and T a hinge de­ composition. Let G be a graph constructed by removing from dual(1-l) each edge { v(h), v(h')} such that there exists two distinct nodes of T, say H and H', such that h E H and h' E H'.

We claim that i) G is a reduct of dual(1-l), and ii) for each hinge H in T, there exists a biconnected component C of G, such that C is the subgraph of G induced by the nodes va(H), i.e. C = duala(H). Moreover, every biconnected component of G corresponds to some hinge, because each node of G is an edge of the original hypergraph, and thus must be contained in some hinge ofT, by definition of hinge de­ composition. Finally, note that the size (number of edges) of any hinge H, is the same as the size (number of nodes) of the corresponding biconnected component C = dual a (H). 0

Combining the above lemma and the results in [Gyssens eta!., 1994], it follows that these two methods identifies the same classes of tractable CSPs.

Theorem 3.2 BICOMPoptd := HINGE.

It is worthwhile noting that, given any hinge decomposition of a hypergraph 1-l, the proof of Lemma 3.1 provides in fact an algorithm for computing an optimal reduct of dual(1-l) with respect to the BICDMP method. For instance, Figure 1 shows a hypergraph 1-l', a hinge decomposition of 1-l', and the opti­ mal reduct of the dual graph obtained by applying the above construction, where dotted edges represent the edges of the dual graph removed in this simplification. Note that the bi­ connected components of this graph correspond to the hinges of the given decomposition. Since biconnected components can be computed in linear time, it follows that a BICOMPoptd decomposition of a hypergraph 1-l can be computed in time O(IN(1-l)ll£(1-l)i2), which is the best known upper bound for computing a hinge decomposition.

Observe that the above result, together with Theorem 2.2, gives us a new insight of the power of TREEWIDTWptd. In­ deed, while the tree decomposition method applied to the pri­ mal graph is incomparable with HINGE [Gottlob et al., 2000], its application to an optimal reduct of the dual graph strongly generalizes HINGE.

Corollary 3.3 HINGE -« TREEWIDTWPtd.

4 Hidden-Variables VS Dual Graph

It is well known that both the dual graph and the hidden­ variable (incidence-graph) representations may be used for identifying tractable classes of non-binary CSPs according to the tree decomposition method (see, e.g., [Kolaitis and Vardi, 2000]). However, it was not clear whether either of these methods generalizes the other one or beats the other one on some classes of CSPs. In this section, we precisely characterize the relationship between TREEWIDTWptd and TREEWIDTHin. First, we observe that there is a CSP class where TREEWIDTWptd is definitely better than TREEWIDTHin.

Theorem 4.1 TREEWIDTWptd C> TREEWIDTHin.

Proof. (Sketch.) We show that there is a class of hy­ pergraphs that is tractable w.r.t. TREEWIDTWP 1 d, but not w.r.t. TREEWIDTHin. For any n > 0, let Rose(n) be the hypergraph having n edges { h1 , ... 1 hn} over the nodes {Xl, ... ,Xn,Yl,···,Yn}, such that h; = {X1, .. . ,Xn,Yi}, for each 0 < i ::=; n. Figure 2 shows the graph Rose(4), its incidence graph and a reduct of its dual graph. It can be seen that any optimal reduct of dual(Rose(n)) is a tree and hence its width according to TREEWIDTWptd is 1. On the other hand, the bipartite graph inc(Rose(n)) contains a clique of size n and hence its treewidth is n - 1. It follows that the class {Rose(n) In> 0} has unbounded treewidth. 0

Note that any hypergraph Rose(n) in the above proof is an acyclic hypergraph. It follows that the class of all acyclic CSP instances is not tractable according to TREEWIDTHin.

Even though TREEWIDTWptd beats TREEWIDTHin, we next shows that TREEWIDTWP 1 d does not generalize TREEWIDTHin.

Theorem 4.2 TREEWIDTHin -fr< TREEWIDTWP 1 d.

Proof. (Sketch.) We show that there is a class of hypergraphs Subset( k) such that the treewidth of the incidence graph is k, but the treewidth of any optimal reduct of dual(Subset(k)) is (k/3) 2 . For any k, the hypergraph Subset(k) is such that N(Subset(k)) = XU Y U Z, where X = {X1, ... , Xm}, Y = {Y1, ... , Ym}, and Z = {Z1, ... , Zm}, with m = k/3.

There are m 2 distinct edges, each containing m - 1 nodes from X, m - 1 nodes from Y, and m - 1 nodes from Z . In particular, each edge e contains one of them subsets of m- 1

elements from X and one the m subsets of m - 1 elements from Y. These subsets may be identified by means of two integers, say a and b, ranging from 0 to m - 1. Similarly, the edge contains a subset of variables from Z identified by an integer c and functionally determined by a and b as follows: c = (a + b )mod m. Thus, each edge e is simply denoted as a triple (a, b, c).

Note that the incidence treewidth of Subset(k) is k. For instance, Figure 3 shows a tree decomposition of the inci­ dence graph of Subset(9), where m = 3. Moreover, it can be proved that the dual graph dual(Subset(k)) cannot be re­ duced and contains a clique of size m 2 = ( k /3) 2 . It follows that its treewidth is (k/3) 2 . o

To give a complete picture of the relationship between TREEWIDTHoptd and TREEWIDTHin, we next show that any decomposition of the incidence graph with width k can be modified to be a decomfosition of a reduct of the dual graph having width at most 2 . Thus, TREEWIDTHin does not beat TREEWIDTWptd.

The algorithm is shown in Figure 4. It takes a tree decom­ position TD = (T, x) of inc(1i), and outputs a tree decom­ position TD' = (T, x') of a suitable reduct of dual(1i).

It performs a breadth-first visit ofT. For each visited node p, we compute the labelling x' (p) of this node in the new tree decomposition TD' from its label x(p) in the given tree decomposition TD: Let x(p) = Vp U Cp, where Vp ~ N(1i) and Cp ~ £ (1i). Then, x' (p) contains all edges in Cp plus one arbitrarily chosen edge hv' that covers V' (i.e., such that V' ~ hv' ), for each subset V' of Vp. This way, p is now labelled only by edges of 1i (i.e., nodes of the dual graph). Moreover, the algorithm forces all such edges hv' to belong to the x' labellings of any vertex q in the subtree rooted at p such that V' ~ x(q).

Note that, if (T, x) has width k, then (T, x') has width at most 2k. Then, from this algorithm (whose proof of correct­ edness is omitted), we get the following relationship.

Theorem 4.3 TREEWIDTHin .f>TREEWIDTWptd.

5 A 2-approximation of TREEWIDTWptd

In this section, we face the problem of computing an optimal reduct of a dual graph in order to get the minimum possi­ ble treewidth. We recall that it is not known whether this problem is feasible in polynomial time or not [Kolaitis and Vardi, 2000]. Moreover, we provide a qualitative explana­ tion of the remarkable difference between TREEWIDTWptd and hypergraph-based notions such as query width and hy­ pertree width.

Let k > 0 be a fixed constant and 1i be a constraint hyper­ graph. Figure 5 shows the Algorithm k-TREE-APPROX that, if the optimal treewidth of dual (1i) is at most k, outputs in polynomial time a tree decomposition of width at most 2k of some reduct of dual(1i) .

LetS be a subset of nodes of dual (1i). A non-empty set C of nodes of dual (1i) is [S]-connected if, for each pair h , h' E C, there exists a path h = h1 , ... , hn = h' in dual (1i) such that h; n hi+l <;f; z, for every z E S . The [S]-components of dual(1i) are the maximal [S]-connected sets of nodes of dual(1i) .

Roughly, k-TREE-APPROX is based on a recursive proce­ dure kDecomp that, given a vertex panda [x(p) ]- component C to be "decomposed," computes the labelling x( q) of a child q of p chosen to deal with C. Then, it recursively call itself for computing the subtree rooted at q that should cover all the x(q)-components included in c.

Finally, if the output (T, x) of kDecomp is not a tree de­ composition of some reduct of dual(1i), then the MAIN module of the algorithm computes a new labelling x' that is guaranteed to be a legal tree decomposition.

The proof of the following theorem is quite involved and will be omitted for space limitation.

Theorem 5.1 Let k be a fixed integer. Given any hyper­ graph 1i, if there exists a reduct of dual (1i) having treewidth bounded by k, then k-TREE-APPROX computes in LLOGCFL a tree decomposition of some reduct of dual (1i) having width at most 2k.

It is worthwhile noting that the output (T, x) of kDecomp, even if it is not a tree decomposition, is in fact a new kind of structural decomposition, defined below, that we call weak query decomposition.

Definition 5.2 A weak query decomposition of a hypergraph 1i is a pair (T, A), where T = (N, E) is a tree, and A is a labelling function which associates to each vertex p E N a set >-.(p) ~ £ (1-l), such that the following conditions hold:

1. for each edges h of 1-l, there exists p E N such that hE >-.(p);
2. for each edge h of 1-l, the set {p E N I h E >-.(p)} induces a (connected) subtree ofT;
3. for each pair of vertices v, v' ofT and each pair of edges h E >-.( v ), h' E >-.( v') there is a path P connecting v and v' in T such that, for each v in P, there exists h" E >-.( v) such that f. ( { h, h'}) ~ h".

The width of the weak query decomposition (T, >-.) is maxpENI>-.(p)l. The weak query-width wqw(1l) of1l is the minimum width over all its weak query decompositions.

Note that Condition 3 above entails the usual connected­ ness condition 3': for each variable Y E N(1l), the set {p E N I Y occurs in some edge h E >-.(p)} induces a (connected) subtree ofT. Thus, any weak query decom­ position of a hypergraph is also a query decomposition of the hypergraph, and thus any class of CSPs having bounded weak query-width is tractable, i.e., can be solved in polyno­ mial time. However, unlike query decompositions [Gottlob et al., 2002], weak query decompositions are efficiently com­ putable. Indeed, LOGCFL is not only included in polynomial time, but also in NC 2 , and thus it contains highly paralleliz­ able problems. Moreover, this new notion has essentially the same "decomposition power" as TREEWIDTWP 1 d.

Theorem 5.3 For any hypergraph 1-l,

Thus, TREEWIDTWP 1 d and the notion of weak query de­ composition are almost equivalent, up to a bounded differ­ ence in favor of the latter method.

Remark. The results in this section shed some light on the difference between the "decomposition power" of TREEWIDTWptd and the strictly more general methods of query and hypertree decompositions. Note that the crucial condition to be maintained in all these tree-structured decom­ positions is the connectedness condition for the constraint variables, and looking at Condition 3 and Condition 3' above we can make the following observation: while in the weak query decompositions (and similarly in TREEWIDTWP 1 d) each hyperedge in the labelling of a tree node plays an indepen­ dent role, in query decompositions (and hypertree decompo­ sitions) all such edges contribute together to maintain the con­ nectedness condition. That is, these hypergraph based notions exploit the union of the hyperedges labelling any tree-node, while the TREEWIDTWptd and the weak query width methods exploit the power of each hyperedge separately.