Backtracking Procedures for Hypertree, HyperSpread and Connected Hypertree Decomposition of CSPs

1 Introduction

A CSP decomposition method DM is tractable if, for a fixed k, determining whether the DM-width of a CSP instance is at most k takes polynomial time and all the CSP instances having DM-width at most k can be solved in polynomial time. A method DM1 is more general than an another method DM2 if all the CSP instance classes having bounded DM2-width also have bounded DM1-width but not vice-versa. Likewise, DM1 is better than DM2 if the DM1-width of any instance is at most its DM2-width, and for an instance its DM1-width is smaller than its DM2-width. Among several tractable decomposition methods [Freuder, 1985; Dechter, 2003; Gyssens et al., 1994; Gottlob et al., 2000], the hypertree decomposition has been shown to be the most general [Gottlob et al., 2000]. But no exact procedure for hypertree decomposition has been able to handle instances of realistic sizes. This is mainly due to huge preprocessing in the existing exact methods [Gottlob et al., 1999; Harvey and Ghose, 2003].

We first present a backtracking procedure for hypertree decomposition. We identify isomorphic components of a hypergraph, and use it to speed-up the procedure. We generalize the procedure, the variations of which results in two new tractable decomposition methods: HyperSpread and Connected Hypertree. Finding a tractable decomposition better than hypertree decomposition has been recently stated as an open problem [MAT, 2006]. We show that hyperspread width is bounded by both hypertree width and spread cut width, which gives a simple positive answer to the open problem. In the experiments on several instances our hypertree and connected hypertree decomposition methods result in finding optimal decompositions of many instances, while the previous methods can find optimal decompositions of at most one instance. In our experiments with a given time limit, for all the instances we are able to obtain a connected hypertree decomposition of width at least as small as the obtained hypertree decomposition. We finally state as an open problem whether the connected hypertree width of an instance equals the hypertree width.

The next section lists necessary definitions. The Section 3 presents the backtracking procedure and defines isomorphic components. The generic procedure and its variants are presented in the Section 4. The Section 5 presents the experimental results. The Section 6 concludes the paper.

2 Definitions

A constraint satisfaction problem instance (CSP) is a triple (V ,D,C), where V is a set of variables, D is a set of domains and C is a set of constraints. A variable vi ∈ V can take values in the finite domain di ∈ D. A constraint ci ∈ C is a pair (si,ri), where si ⊆ V is the scope of the constraint and ri is a relation over si. The ri restricts the allowed combination of values the variables in si can be assigned. A solution to a CSP is an assignment of values to all the variables in the CSP, such that the assignment restricted to a scope si belongs to the relation ri. A CSP is satisfiable if there is a solution for the CSP.

A constraint hypergraph of a CSP (V ,D,C) is a hypergraph H = (V ,E), where the set of nodes in the hypergraph V is the same as the set of variables in the CSP. For each (si,ri) ∈ C, there will be an edge (also called a hyperedge) ei ∈ E, such that ei = si, i.e., E = {si | (si, ri) ∈ C}. Hereafter, just the term hypergraph refers to a constraint hypergraph. For a set of edges K ⊆ E, let the term vars(K) = ⋃e∈K e, i.e., the union of variables occurring in the edges K. For a set of variables L ⊆ V , let the term edgeVars(L) = vars({e | e ∈ E, e ∩ L ̸= ∅}), i.e., all the variables occurring in a set of edges, where each edge in the set contains at least one variable in L.

A tree decomposition [Robertson and Seymour, 1986; Dechter, 2003] of a hypergraph (V ,E) is a pair TD = (T ,γ), where T = (N,A) is a tree and γ is a mapping which for each node n ∈ N associates γ(n) ⊆ V . Additionally, a tree decomposition has to satisfy two properties: (1) ∀e ∈ E. ∃n ∈ N. e ⊆ γ(n), and (2) ∀v ∈ V , the nodes {n | n ∈ N, v ∈ γ(n)} induces a connected subtree in T . A hypertree [Gottlob et al., 2000] of a hypergraph (V ,E) is a triple (T ,χ,λ), where T = (N,A) is a rooted tree. The χ and λ are mappings that associate for each node n ∈ N, χ(n) ⊆ V and λ(n) ⊆ E. If T ′ = (N ′ , A′ ) is a subtree of T , then χ(T ′) = ⋃n∈N ′ χ(n). Let the term Tn denote the subtree rooted at the node n ∈ N. Let the term nodes(T) = N. The width of the hypertree (T ,χ,λ) is max {|λ(n)| | n ∈ nodes(T )}.

A hypertree decomposition [Gottlob et al., 2000] of a hypergraph H is a hypertree HD = (T ,χ,λ), which has to satisfy the three properties: (1) (T ,χ) is a tree decomposition of H, (2) ∀n ∈ nodes(T), χ(n) ⊆ vars(λ(n)), and (3) ∀n ∈ nodes(T), χ(Tn) ∩ vars(λ(n)) ⊆ χ(n). The hypertree width of H, denoted htw(H), is the minimum width of all possible hypertree decompositions of H.

To simplify the presentation, we assume that H is connected. Given a set of variables P ⊆ V , and two variables m, n ∈ V , the variables m and n are [P]-adjacent if ∃e ∈ E. m, n ∈ (e\P). A set of variables Q ⊆ V is [P]-connected, if for any two variables m, n ∈ Q, there is a sequence of variables m = l1, l2, . . . , lr-1, lr = n, such that, for each i ∈ [1, r - 1], li and li+1 are [P]-adjacent. A set of variables Q ⊆ V is a [P]-component (or [P]-comp in short), if it is a maximal [P]-connected subset of V . Let [P]- components (or [P]-comps in short) denote the set containing every [P]-component.

Given an integer k and α ⊆ E, α is a k-edge, if |α| ≤ k. Let the set k-edges = {α | α ⊆ E, |α| ≤ k}, i.e, the set containing every k-edge. Given a k-edge α, an α-comp is a [vars(α)]-comp. The size of α-comps, which contains every α-comp, is at most |E|, as for every α-comp edgeVars(αcomp) will uniquely contain at least one edge e ∈ E. Given a set of variables Q ⊆ V , the sub-hypergraph induced by Q is the hypergraph (V ′ ,E′ ), where V ′ = Q and E′ = {e ∩Q | e ∈ E}. Let a pair of the form (α,α-comp), where α is a k-edge, be called a k-edge-component.

3 The Backtracking Procedure

Our procedure is shown in Figure 1. The main procedure IsDecomposable takes the pair ((V ,E), k) as input. The output is a hypertree decomposition if htw((V ,E)) ≤ k, otherwise the message 'Not-k-decomposable'.

Given a k-edge-component (α,α-comp), we say the pair (α,α-comp) is k-decomposable iff the sub-hypergraph induced by the nodes in edgeVars(α-comp) has a hypertree decomposition HD' of width at most k, such that, if the root node of HD' is r, then edgeVars(α-comp) \ α-comp ⊆ χ(r). Essentially, the notion k-decomposable tells us whether the sub-hypergraph can be decomposed into a HD' of width at most k, such that HD' can be used as a block in building a decomposition for the whole hypergraph. Hence, the pair (∅,V ) is k-decomposable iff the htw((V ,E)) ≤ k. We say that the

(α,α-comp) is k-decomposable by using the k-edge β if there exists a HD' with λ(r) = β.

The procedure AddGood is used to add a tuple (α,αcomp,β,cCs) to the set goods, if the pair (α,α-comp) is kdecomposable by using the k-edge β. The set cCs in the tuple, denotes the elements of β-comps contained in α-comp. Similarly, the procedure AddNoGood is used to add a pair (α,α-comp) to the set noGoods, if the pair (α,α-comp) is not k-decomposable. The procedure IsGood(α,α-comp) returns true iff a tuple of the form (α,α-comp,β,cCs) exists in the set goods. Similarly, the procedure IsNoGood(α,α-comp) returns true iff the pair (α,α-comp) exists in the set noGoods.

The procedure Decompose takes a (α,α-comp) pair as input and returns true iff (α,α-comp) is k-decomposable. The line(1) of the procedure finds cv, the set of variables through which the α-comp is connected to the rest of the variables in the hypergraph. The loop that begins at line(2) iterates for every k-edge β, such that (vars(β) ∩ α-comp ̸= ∅) and (cv ⊆ vars(β)). That is the β should be such that vars(β) contains at least one variable in α-comp, and cv is contained in vars(β). The set cCs in line(3) is the set of elements of βcomps, which are contained in α-comp and hence necessary for consideration by the Decompose procedure.

The internal loop starting at line(5) of Decompose checks whether a (β,cC) pair is k-decomposable. The variable success will be true at the line(10) iff, for each cC ∈ cCs, the pair (β,cC) is k-decomposable. A call to Decompose(β,cC) at line(8) is made iff both the calls to IsNoGood(β,cC) and IsGood(β,cC) return false. This makes sure that for any (β,βcomp) pair, the call Decompose(β,β-comp) is made at most once. At line(10), if the variable success is set to true, then the tuple (α,α-comp,β,cCs) is added to the set goods and the procedure returns true. Otherwise, the loop at line(2) continues with an another k-edge choice for β. If all choices for β at line(2) is exhausted without any success, then the procedure adds the (α,α-comp) pair to the set noGoods at line(11) and then returns false.

In case the call Decompose(∅,V ) at line(1) of the procedure IsDecomposable returns true, then a hypertree decomposition (HD) is built and returned. Otherwise, a message 'Notk-decomposable', meaning the hypertree width of (V ,E) is larger than k, is returned. At line(2) of the procedure a root node r is created and a tuple of the form (∅,V ,β,cCs) is obtained from the set goods. The third entry β in the tuple corresponds to the k-edge used during the first call of the recursive Decompose procedure. Hence, λ(r) is set to β. By the definition of hypertree decomposition, for a root node r, χ(r) = vars(λ(r)). Hence, the χ(r) is set to vars(β). In the lines(4-5), for each cC ∈ cCs, a child node of r is created by the call BuildHypertree (β,cC,r). The procedure BuildHypertree in fact recursively calls itself and extracts, from the set goods, the subtree rooted at a child vertex of r. At line(6), the procedure returns a hypertree decomposition.

Theorem3.1. IsDecomposable(H,k) returns a hypertree decomposition iff htw(H) ≤ k.

The proof of the above theorem follows from the fact that, our procedure is essentially a backtracking version of the optk-decomp [Gottlob et al., 1999] procedure for hypertree de- Set goods = ∅; Set noGoods = ∅; Hypertree HD = (T ,λ,χ)

1: ∀ (tw,tx,ty,tz) ∈ goods 2: if (t1,t2) = (tw,tx) then return true 3: return false IsNoGood (t1,t2) 1: ∀ (tx,ty) ∈ noGoods 2: if (t1,t2) = (tx,ty) then return true 3: return false AddGood (t1,t2,t3,t4) 1: goods = goods ∪ {(t1, t2, t3, t4)} AddNoGood (t1,t2) 1: noGoods = noGoods ∪ {(t1, t2)} BuildHypertree (α,α-comp,s) 1: Find (α,α-comp,β,cCs) ∈ goods 2: Add a node t to T as a child node of s 3: λ(t) = β; χ(t) = (vars(β) ∩ edgeVars(α-comp)) 4: ∀ cC ∈ cCs 5: BuildHypertree (β,cC,t)

Decompose (α,α-comp) 1: cv = vars(α) ∩ edgeVars(α-comp) 2: ∀β ∈ k-edges. (vars(β) ∩ α-comp ̸= ∅). (cv ⊆ vars(β)) 3: cCs = {cC | cC ∈ β-comps, cC ⊆ α-comp } 4: success = true 5: ∀ cC ∈ cCs 6: if (IsNoGood(β,cC)) then success = false 7: else if (IsGood(β,cC)) then continue 8: else if (Decompose(β,cC)) then continue 9: else success = false 10: if (success) then AddGood(α,α-comp,β,cCs); return true 11: AddNoGood(α,α-comp); return false IsDecomposable ((V ,E),k) 1: if (Decompose(∅,V )) then 2: Add root node r to T; Find (∅,V ,β,cCs) ∈ goods 3: λ(r) = β; χ(r) = vars(β) 4: ∀ cC ∈ cCs 5: BuildHypertree (β,cC,r) 6: return HD 7: else return 'Not-k-Decomposable' IsGood (t1,t2)

composition. The opt-k-decomp procedure suffers from a huge pre-processing cost. For a given k, the opt-k-decomp implicitly finds all possible decompositions of width at most k and extracts the optimal one. But our backtracking procedure stops as soon as it discovers a decomposition of width at most k. Hence, our procedure will be able to stop quickly when there are several decompositions of width at most k.

Theorem3.2. The time complexity of IsDecomposable(H,k) is O(|E|3k+3 ).

Proof. The time complexity is dominated by Decompose. During a call to Decompose, the loop over choices for β iterates at most O(|E|k ). The |cCs| is at most |E|. Since each k-edge results in at most |E| k-edge-components, the total number of k-edge-components is O(|E|k+1 ). The cost of each call to IsNoGood/IsGood will take O(|E|k+1 ) time, as the size of goods/noGoods can be at most the number of k-edge-components. We can ignore the cost for calls to AddGood/AddNoGood as their contribution to the complexity is dominated. Hence, the cost for each call to Decompose is O(|E|2k+2 ). There can be at most O(|E|k+1 ) calls to Decompose, at most once for each k-edge-component. Hence, the time complexity of the procedure IsDecomposable is O(|E|3k+3 ).

Given two k-edge-components (α,comp) and (α′ ,comp'), they are isomorphic if comp = comp'.

Theorem 3.3. Given two isomorphic pairs (α,comp) and (α′ ,comp'), (α,comp) is k-decomposable iff (α′ ,comp') is kdecomposable.

Proof. By definition comp = comp'. Hence, the only difference between the calls Decompose(α,comp) and Decompose(α′ ,comp') are the first parameters: α and α′ . In Decompose the distinction between α and α′ is of importance only at line(2), where the set cv is calculated. We now show that cv is independent of α. Since (α,comp) is a k-edge-component, by definition, ∀e ∈ E. e ⊆ edgeVars(comp) ⇒ (e\comp) ⊆ α. Also, comp ∩ vars(α) = ∅. This implies that, during the call Decompose(α,comp), the set cv = edgeVars(comp)\(comp). Therefore, the set cv remains the same during both the calls Decompose(α,comp) and Decompose(α′ ,comp'). Hence, the proof.

For each set of isomorphic components we need to make at most one call to Decompose. Hence, by using isomorphism the number of calls to Decompose may reduce significantly.

4 Variants of Hypertree Decomposition

The Figure 2 presents the pseudo code for a generic decomposition procedure IsDecomposableGe, based on the hypertree framework. There are two changes in the generic procedure from the earlier procedure in Figure 1. First change is that, the generic version is able to detect isomorphism, so that a call to Decompose is made at most once for a set of isomorphic components. The second change is in line(2) of the procedure Decompose, where the code β ∈ k-edges in the old procedure has been replaced with (β,Qβ) ∈ Ω in the generic version. Each element in the set Ω is a pair of the form (β,Qβ), where β ∈ k-edges and Qβ ⊆ vars(β). In all the places where vars(β) was used in the old procedure, Qβ is used in the generic procedure. The set Ω defines, for each β ∈ k-edges, the allowed subsets of vars(β) which can be used for decomposition. Essentially, by allowing subsets of vars(β) to be considered for obtaining a decomposition we obtain a generic procedure. Note, the procedures IsGood, AddGood, IsNoGood, and AddNoGood are not listed in Figure 2 as the old versions of them can be naturally modified to work in the generic framework. Let the set ΩHTD = {(α, vars(α)) | α ∈ k-edges }. We have the following theorem.

Theorem 4.1. When Ω = ΩHTD, IsDecomposableGe(H,k) returns a hypertree decomposition iff htw(H) ≤ k.

Set goods = ∅; Set noGoods = ∅; Hypertree D = (T ,λ,χ)

Decompose (comp) 1: cv = edgeVars(comp) \ comp 2: ∀(β,Qβ) ∈ Ω. (Qβ∩ comp ̸= ∅). (cv ⊆ Qβ) 3: cCs = {cC | cC ∈ [Qβ]-comps, cC ⊆ comp } 4: success = true 5: ∀ cC ∈ cCs 6: if (IsNoGood(cC)) then success = false 7: else if (IsGood(cC)) then continue 8: else if (Decompose(cC)) then continue 9: else success = false 10: if (success) then AddGood(comp,β,Qβ,cCs); return true

• 11: AddNoGood(comp); return false

IsDecomposableGe ((V ,E),k)

1: if (Decompose(V )) then 2: Add root node r to T; Find (V ,β,Qβ,cCs) ∈ goods 3: λ(r) = β; χ(r) = Qβ 4: ∀ cC ∈ cCs 5: BuildHypertree (cC,r) 6: return D

• 7: else return 'Not-k-Decomposable'

BuildHypertree (comp,s)

• 1: Find (comp,β,Qβ,cCs) ∈ goods
• 2: Add a node t to T as a child node of s
• 3: λ(t) = β; χ(t) = (Qβ∩ edgeVars(comp))
• 4: ∀ cC ∈ cCs
• 5: BuildHypertree (cC,t)

Figure 2: The pseudo code of the generic procedure for decomposition in hypertree framework.

4.1 HyperSpread Decomposition

An unbroken guarded block (ug-block) [Cohen et al., 2005] is a pair (α,Qα), where α ⊆ E and Qα ⊆ vars(α), satisfying two conditions: (1) ∀e1, e2 ∈ α. e1 ∩ e2 ⊆ Qα, and (2) each [Qα]-comp has non-empty intersection with at most one [vars(α)]-comp. The size of an ug-block (α,Qα) is |α|.

For some α ⊆ E and v ∈ V , let the label, Lα(v) = {cC | cC ∈ [α]-comps, v ∈ edgeVars(cC)}. An ug-block (α,Qα) is canonical if ∀e ∈ α. ∀v1, v2 ∈ e\Qα. Lα(v1) = Lα(v2). Let ΩHSD be the set of all the at most k sized canonical ug-blocks of (V ,E). Note, by the definition of canonical ug-blocks, ΩHTD ⊆ ΩHSD. Given k and a canonical ug-block (α,Qα) with |α| ≤ k, let a triple of the form (α,Qα,[Qα]- comp) be called a k-spread-component. It has been shown in [Cohen et al., 2005] that, there exists at most (|E| +1)k+2 k-spread-components. The notion of isomorphism can be naturally extended to k-spread-components. Given two kspread-components (α,Qα,comp) and (α′ ,Qα′ ,comp'), they are isomorphic when comp = comp'.

A spread cut [Cohen et al., 2005] of a hypergraph H is a hypertree SC = (T ,λ,χ), satisfying the two conditions: (1) (T ,χ) is a tree decomposition of H, and (2) ∀n ∈ nodes(T), (λ(n),χ(n)) is a canonical ug-block. The spread cut width of H, denoted scw(H), is the minimum width of all possible spread cuts of H.

A hyperspread decomposition of a hypergraph H is a hypertree HSD = (T ,λ,χ), satisfying the two conditions: (1) (T ,χ) is a tree decomposition of H, and (2) ∀n ∈ nodes(T). ∃(α,Qα) ∈ ΩHSD. λ(n) = α. χ(n) = Qα ∩ χ(Tn). The hyperspread width of H, denoted hsw(H), is the minimum width of all possible hyperspread decompositions of H.

Due to a variant of IsDecomposableGe, we have:

Theorem 4.2. When Ω = ΩHSD, IsDecomposableGe(H,k) returns a hyperspread decomposition iff hsw(H) ≤ k.

By arguments similar to those of Theorem 3.2, we have:

Theorem 4.3. When Ω = ΩHSD, the time complexity of IsDecomposableGe(H,k) is O((|E| + 1)3k+7 ).

Given a hyperspread decomposition of a CSP, the CSP can be solved by the same algorithm for CSP solving using hypertree decompositions [Gottlob et al., 2000]. Also, for a fixed k, determining whether hsw of CSP is ≤ k takes polynomial time. Hence, the hyperspread decomposition is tractable.

We now state that the hyperspread width is bounded by both hypertree width and the spread cut width.

Theorem 4.4. hsw(H) ≤ htw(H) and hsw(H) ≤ scw(H)

Proof. The last two conditions in the definition of hypertree decomposition implies that: ∀n ∈ nodes(T). ∃(α,Qα) ∈ ΩHTD. λ(n) = α. χ(n) = Qα ∩ χ(Tn). Since for any k, ΩHTD ⊆ ΩHSD, each hypertree decomposition is also a hyperspread decomposition. Hence, hsw(H) ≤ htw(H).

The second condition in the definition of spread cut implies that: ∀n ∈ nodes(T ). ∃(α, Qα) ∈ ΩHSD. λ(n) = α. χ(n) = Qα. Therefore, each spread cut is also a hyperspread decomposition. Hence, hsw(H) ≤ scw(H).

Recently in [MAT, 2006], the existence of a tractable decomposition better than hypertree decomposition was stated as an open problem. In [Cohen et al., 2005], a family of hypergraphs Hn, for n = 1, 2, . . . , was presented for which the hypertree width of Hn is at least 3n, while the spread cut width is at most 2n. Note, it is not known whether for any H, scw(H) ≤ htw(H). Since for any H, hsw(H) ≤ htw(H) and hsw(Hn) ≤ scw(Hn) < htw(Hn) , hyperspread decomposition gives a simple positive answer to the open problem.

4.2 Connected Hypertree Decomposition

A connected hypertree decomposition is a hypertree decomposition CHTD = (T ,λ,χ), satisfying two conditions: (1) for the root node r of T , |λ(r)| = 1, and (2) if c ∈ nodes(T) is a non-root node and the parent node of c is p, then ∀e ∈ λ(c). ∃v ∈ χ(c) ∩ χ(p). v ∈ e. The second condition states that for any non-root node c with parent node p, each edge e in λ(c) should have at least one variable that is common to both χ(c) and χ(p). The two conditions in the definition results in a significant reduction of the branching choices in the procedure Decompose. We show empirical results in the next section to support such reduction. Let the connected hypertree width of a hypergraph H, denoted chtw(H), be the minimum width of the all possible connected hypertree decompositions of H. By definitions, htw(H) ≤ chtw(H). It is an open problem whether chtw(H) = htw(H).

Let ΩCHTD(cv) = {(α, vars(α)) | α ∈ k-edges, (cv = ∅) ⇒ (|α| = 1), (cv ̸= ∅) ⇒ (∀e ∈ α. ∃v ∈ cv. v ∈ e)}, where cv ⊆ V corresponds to the connection variables in the procedure Decompose. As an another variant of the generic decomposition procedure, we state the following theorem.

Theorem 4.5. When Ω = ΩCHTD(cv), a connected hypertree decomposition is returned by IsDecomposableGe(H, k) iff chtw(H) ≤ k.

Unlike the previous two variants of the generic decomposition procedure, when Ω = ΩCHTD(cv), the set Ω is newly defined during each call to Decompose based on the connection variables cv.

Since connected hypertree decompositions are subsets of hypertree decompositions, connected hypertree decomposition is tractable.

5 Experiments

We have implemented the presented backtracking procedures for both hypertree decomposition and connected hypertree decomposition. We have not implemented the hyperspread decomposition procedure, which does not seem easy to implement. We plan to do it in the future. All of our experiments are done on an Intel Xeon 3.2Ghz machine, running Linux and with 4GB RAM. We use 12 instances in our experiments. They are constraint hypergraphs from different sources: five from configuration problems (*.cp), five from fault trees (*.dag), and two from SMT instances (*.smt). Our tools and instances are available online 1 .

In our implementation, for a given Ω and H = (V,E), we find an optimal decomposition by a sequence of queries to the procedure IsDecomposableGe(H,k). The parameter k will take values in the sequence k1, k2, . . . , kl-1, kl. In the sequence, k1 = |E|. If the query IsDecomposableGe(H,ki) returns a decomposition of width k′ , then ki+1 = k′ - 1. If the query IsDecomposableGe(H,ki) returns the message 'Not-k-Decomposable', then l = i. The optimal width will be kl + 1. We found that the l is often very small due to jumps the sequence could make. The results of our experiments are listed in Table 1. All the experiments in the table are done with a time limit of 1800 CPU seconds. The legend 'CHTD' ('HTD') refers to the experiments with Ω = ΩCHTD (Ω = ΩHTD). The legend 'CHTD-NoIso' ('HTD-NoIso')

refers the 'CHTD' ('HTD') procedure without detection of isomorphic components. For each method, we list the best width obtained. In the cases we are able to prove optimality, the entries in the width columns will be of the form k∗. We also tested the heuristic 'BE' in the HTDECOMP 2 tool. The BE uses tree decomposition heuristics and set covering heuristics to obtain a heuristic Generalized Hypertree Decomposition (GHTD) [Gottlob et al., 2003]. In case of a GHTD, the third condition in the definition of hypertree decomposition may be violated. Since BE is randomized, we ran experiments using BE five times, and list in the table the mean time (μT), the mean width (μW) and the best width (MinW). We also did experiments on a hybrid BE+CHTD, in which five runs of BE will be used to first obtain five GHTDs. If the best width of the GHTDs so obtained is kbe, then the CHTD procedure will be invoked with k1 = kbe. Note, the best width decomposition found by the hybrid BE+CHTD may be a GHTD, whose width can be smaller than htw. Although, the HTDECOMP tool has heuristic choices other than BE, we choose BE since we think it is the best choice. The BE+CHTD combination can be naturally extended with any initialization heuristic. The last row, #optimal of the table lists the number of proven optimal width decompositions obtained by each method. Note, to prove optimality, the query corresponding to kl needs to return 'Not-k-decomposable' within the time limit.

All the exact methods listed in the table are our contributions. The experiments using the implementations 3 of the previous exact methods opt-k-decomp, and an improvement over opt-k-decomp, red-k-decomp [Harvey and Ghose, 2003], either exceeded time limit or aborted in all cases except renault.cp, in which red-k-decomp took 1257 seconds to find an optimal decomposition. In fact, both the experiments using the opt-k-decomp and red-k-decomp tools consisted of only one query to the tool. For an instance H, if the 'CHTD' finds a decomposition of width k′ in 1800 seconds, then the opt-k-decomp and red-k-decomp are just asked to find a decomposition of width k′ . Hence, the experiments are done in a favorable setting to the previous methods.

From the table, we can observe that the CHTD procedure Width gives more optimal decompositions than others. In none of the instances the HTD could find a better decomposition than that of CHTD. In three instances the BE finds GHTDs of width smaller than those by the exact methods. For use in practice the hybrid BE+CHTD seems the best choice, as it results in best decomposition in all the cases.

2 http://www.dbai.tuwien.ac.at/proj/hypertree/downloads.html

3 http://www.dsl.uow.edu.au/˜harvey/research hypertrees.shtml

Figure 4: The effect of detecting isomorphism and CHTD vs. HTD in isp9603 instance (time limit 10000 seconds).

In Figure 3, we plot the time taken for the queries IsDecomposableGe(H,k) with Ω = ΩCHTD, k ∈ {1, 2, . . . , 11, 12} and H being one among the eight instances for which CHTD succeeds in obtaining optimal decompositions within 1800 seconds. We can observe that, for each instance H, the cost of queries until k ∗-1, where k∗ is chtw(H), increases exponentially. The cost suddenly decreases at k∗ and continues to decrease exponentially.

In Figure 4, we plot the results of queries on the four different exact procedures for the instance isp9603, with time limit 10000 seconds. The plot shows a huge benefit of identifying isomorphism. The plot also shows an exponential difference between the runtime of CHTD and HTD which is due to the branching restrictions in CHTD. The HTD and HTD-NoIso timed out for some queries.

6 Conclusion

We have presented a backtracking procedure for hypertree decomposition and defined isomorphism to speed-up the procedure. We generalized the procedure, the variants of which results in two new tractable decompositions: hyperspread and connected hypertree. We have shown that hyperspread width is bounded by both hypertree width and spread cut width, which solves a recently stated open problem. The experiments using our methods are able to find optimal decompositions of several instances.

Avenues for future work include: implementation of hyperspread decomposition, determining chtw = htw?, identifying other tractable variants, and comparison with exact methods for tree decomposition like [Gogate and Dechter, 2004].