Fast and Parallel Decomposition of Constraint Satisfaction Problems

1 Introduction

Many real-life tasks can be effectively modelled as CSPs, giving them a vital importance in many areas of Computer Science. As solving CSPs is a classical NP-complete problem, there is a large body of research to find tractable fragments. One such line of research focuses on the underlying hypergraph structure of a CSP instance. A key result in this area is that CSP instances whose underlying hypergraph is acyclic, can be solved in polynomial time [Yannakakis, 1981]. Several generalisations of acyclicity have been identified by defining various forms of hypergraph decompositions, each associated with a specific notion of width [Gottlob et al., 2000; Cohen et al., 2008]. Intuitively, the width measures how far away a hypergraph is from being acyclic, with a width of 1 describing the acyclic hypergraphs.

In this work, we focus on Generalized Hypertree Decompositions (GHD) [Gottlob et al., 2009], and generalized hypertree width (ghw). The computation of GHDs is itself intractable in the general case, already for width 2 [Fischl et al., 2018]. However, for (hypergraphs of) CSPs with realistic restrictions, this problem becomes tractable. One such restriction is the bounded intersection property (BIP), which requires that any two constraints in a CSP only share a bounded number of variables [Fischl et al., 2018]. Indeed, by examining a large number of CSPs from various benchmarks and real-life applications, it has been verified that this intersection of variables tends to be small in practice [Fischl et al., 2019]. In that work, over 3,000 instances of hypergraphs of CSPs and also of Conjunctive Queries (CQs) were examined and made publicly available in the HyperBench benchmark at http://hyperbench.dbai.tuwien.ac.at The use of such decompositions can speed up the solving of CSPs and also the answering of CQs significantly. In fact, in [Aberger et al., 2016] a speed-up up to a factor of 2,500 was reported for the CQs studied there. Structural decompositions are therefore already being used in commercial products and research prototypes, both in the CSP area as well as in database systems [Aberger et al., 2016; Aref et al., 2015; Amroun et al., 2016; Habbas et al., 2015; Lalou et al., 2009]. However, previous decomposition algorithms are limited in that they fail to find optimal decompositions (i.e., decompositions of minimal width) even for low widths. This is also the case for various GHD computation methods proposed in [Fischl et al., 2019; Fichte et al., 2018]. The overall aim of our work is therefore to advance the art of computing hypergraph decompositions and to make the use of GHDs for solving CSPs applicable to a significantly wider range of CSP instances than previous methods. More specifically, we derive the following research goals:

Main Goal: Provide major improvements for computing hypergraph decompositions.

As part of this main goal, we define in particular:

• Sub-goal 1: Design novel parallel algorithms for structural
• decompositions, in particular GHDs, and

Sub-goal 2: put all this to work, by implementing and extensively evaluating these improvements.

As a first step in pursuing the first goal, we aim at generally applicable simplifications of hypergraphs to speed up the decomposition of hypergraphs. Here, "general applicability" means that these simplifications can be incorporated into any decomposition algorithms such as the ones presented in [Fichte et al., 2018; Fischl et al., 2019] and also earlier work such as [Gottlob and Samer, 2008]. Moreover, we aim at heuristics for guiding the decomposition algorithms to explore more promising parts of the big search space first.

However, it will turn out that these simplifications and heuristics are not sufficient to overcome a principal shortcoming of existing decomposition algorithms, namely their sequential nature. Modern computing devices consist of multicore architectures, and we can observe that single-core performance has mostly stagnated since the mid-2000s. So to produce programs which run optimally on modern machines, one must find a way of designing them to run efficiently in parallel. However, utilising multi-core systems is a nontrivial task, which poses several challenges. In our design of parallel GHD-algorithms, we focus on three key issues:

• i minimising synchronisation delay as much as possible,
• ii finding a way to partition the search space equally among CPUs, and thus utilising the resources optimally,
• iii supporting efficient backtracking, a key element of all structural decomposition algorithms presented so far.

In order to evaluate our algorithmic improvements and our new parallel GHD-algorithms, we have implemented them and tested them on the publicly available HyperBench benchmark mentioned above. For our implementation, we decided to use the programming language Go proposed by Google [Donovan and Kernighan, 2015], which is based on the classical Communication Sequential Processes pattern by [Hoare, 1978], since it reduces the need for explicit synchronisation.

To summarise the main results of this work:

• We have developed three parallel algorithms for computing GHDs, where the first two are loosely based on the balanced separator methods from [Akatov, 2010; Fischl et al., 2019]. Moreover, we have designed a hybrid approach, which combines the strengths of parallel and sequential algorithms. This hybrid approach ultimately proved to be the best.
• In addition to designing parallel algorithms, we propose several algorithmic improvements such as applying multiple pre-processing steps on the input hypergraphs and using various heuristics to guide the search for a decomposition. Moreover, for the hybrid approach, we have explored when to best switch from one approach to the other.
• We have implemented the parallel algorithms together with all algorithmic improvements and heuristics presented here. The source code of the program is available under https://github.com/cem-okulmus/BalancedGo. With our new algorithms and their implementation, dramatically more instances from HyperBench could be solved compared with previous algorithms. More specifically, we could extend the number of hypergraphs with exact ghw known by over 50%. In total, this means that for over 75% of all instances of HyperBench, the exact ghw is now known. If we leave aside the randomly-generated CSPs, and focus on the those from real world applications, we can show an increase of close to 100%, almost doubling the number of instances solved.

Our work therefore makes it possible to compute GHDs efficiently on modern machines for a wide range of CSPs. It enables the fast recognition of low widths for many instances encountered in practice (as represented by HyperBench) and thus lays the foundation for more systems and applications in evaluating CSPs and CQs based on their structural properties.

The remainder of this paper is structured as follows: In Section 2, we provide the needed terminology and recall previous approaches. In Section 3, we present our main algorithmic contributions. This is followed by presenting experimental evaluations in Section 4. In Section 5, we summarise our main results and highlight directions for future work.

2 Preliminaries

CSPs & Hypergraphs. A constraint satisfaction problem (CSP) P is a set of constraints (Si,Ri), where Si is a set of variables and Ri a constraint relation which contains the valid combination of values that variables in Si can take. A solution to P is a mapping of variables to values, such that for each constraint we map the variables to a corresponding combination in its constraint relation. A hypergraph H is a tuple (V (H),E(H)), consisting of a set of vertices V (H) and a set of hyperedges (synonymously, simply referred to as "edges") E(H) ⊆ 2V (H) . To get the hypergraph of a CSP P , we consider V (H) to be the set of all variables in P , and each Si to be one hyperedge. A hypergraph H is said to have the bounded intersection property (BIP), if there exists a constant c such that for any two edges e1, e2 ∈ E(H), e1 ∩ e2 ≤ c.

Decompositions. A GHD of a hypergraph H = (V (H),E(H)) is a tuple 〈T, χ, λ〉, where T = (N,E(T)) is a tree, and χ and λ are labelling functions, which map to each node n ∈ N two sets, χ(n) ⊆ V (H) and λ(n) ⊆ E(H). For a node n we call χ(n) the bag, and λ(n) the edge cover of n. We denote with B(λ(n)) the set {v ∈ V (H) | v ∈ e, e ∈ λ(n)}, i.e., the set of vertices "covered" by λ(n). The functions χ and λ have to satisfy the following conditions:

1. For each e ∈ E(H), there is a node n ∈ N s.t. e ⊆ χ(n).
2. For each vertex v ∈ V (H), {n ∈ N | v ∈ χ(n)} is a connected subtree of T .
3. For each node n ∈ N, we have that χ(n) ⊆ B(λ(n)).

The width of a GHD is defined as max{|λ(n)| : n ∈ N}. The generalized hypertree width (ghw) of a hypergraph is the smallest width of any of its GHDs. Deciding if ghw(H) ≤ k for a hypergraph H and fixed k is NP-complete, as one needs to consider exponentially many possible choices for the bag χ(n) for a given edge cover λ(n).

It was shown in [Fischl et al., 2019] that for any class of hypergraphs enjoying the BIP, one only needs to consider a polynomial set of subsets of hyperedges (called subedges ) to compute their ghw.

Components & Separators. Consider a set of vertices W ⊆ V (H). A set C of vertices with C ⊆ V (H) \ W is [W]-connected if for any two distinct vertices v,w ∈ C there exists a sequence of vertices v = v0, . . . , vh = w and a sequence of edges e0, . . . , eh-1 (h ≥ 0) such that {vi, vi+1} ⊆ (ei \ W), for each i ∈ {0, . . . , h - 1}. A set C ⊆ V (H) is a [W]-component, if C is maximal [W]- connected. For a set of edges S ⊆ E(H), we say that C is "[S]-connected" or an "[S]-component" as a short-cut for C is "[W]-connected" or a "[W]-component", respectively, with W = ⋃e∈S e. We also call S a separator in this context. The size of an [S]-component C is defined as the number of edges e ∈ E(H) such that e∩C ̸= ∅. For a hypergraph H and a set of edges S ⊆ E(H), we say that S is a balanced separator if all [S]-components of H have a size ≤ |E(H)| 2 .

It was shown in [Adler et al., 2007] that, for every GHD 〈T, χ, λ〉 of a hypergraph H, there exists a node n ∈ N such that λ(n) is a balanced separator of H. This property can be made use of when searching for a GHD of size k of a hypergraph H as we shall recall in Section 2.2 below.

2.1 Computing Hypertree Decompositions (HDs)

We briefly recall the basic principles of the Det-K-Decomp program from [Gottlob and Samer, 2008] for computing Hypertree Decompositions (HDs), which was the first implementation of the original HD algorithm from [Gottlob et al., 2002]. HDs are GHDs with an additional condition to make their computation tractable in a way explained next.

For fixed k ≥ 1, Det-K-Decomp tries to construct an HD of a hypergraph H in a top-down manner. It thus maintains a set C of vertices, which is initialised to C := V (H). For a node n in the HD (initially, this is the root of the HD), it "guesses" an edge cover λ(n), i.e., λ(n) ⊆ E(H) and |λ(n)| ≤ k. For fixed k, there are only polynomially many possible values λ(n). Det-K-Decomp then proceeds by determining all [λ(n)]-components Ci with Ci ⊆ C. The additional condition imposed on HDs (compared with GHDs) restricts the possible choices for χ(n) and thus guarantees that the [λ(n)]- components inside C and the [χ(n)]-components inside C coincide. This is the crucial property for ensuring polynomial time complexity of HD-computation - at the price of possibly missing GHDs with a lower width.

Now let C1, . . . ,Cℓ denote the [λ(n)]-components with Ci ⊆ C and let E1, . . . ,Eℓ denote subsets of E(H) with Ei = {e | e ∩ Ci ̸= ∅} for every i. By the maximality of components, these sets Ei are pairwise disjoint. Moreover, it was shown in [Gottlob et al., 2002] that if H has an HD of width ≤ k, then it also has an HD of width ≤ k such that the edges in each Ei are "covered" in different subtrees below n. More precisely, this means that n has ℓ child nodes n1, . . . , nℓ, such that for every i and every e ∈ Ei, there exists a node ne in the subtree rooted at ni with e ⊆ χ(ne). Hence, Det-K-Decomp recursively searches for an HD of the hypergraphs Hi with E(Hi) = Ei and V (Hi) = ⋃ Ei with the slight extra feature that also edges fromE\Ei are allowed to be used in the λ-labels of these HDs.

2.2 Computing GHDs

It was shown in [Fischl et al., 2018] that, even for fixed k = 2, deciding if ghw(H) ≤ k holds for a hypergraph H is NPcomplete. However, it was also shown there that if a class of hypergraphs satisfies the BIP, then the problem becomes tractable. The main reason for the NP-completeness in the general case is that, for a given edge cover λ(n), there can be exponentially many bags χ(n) satisfying condition 3 of GHDs, i.e., χ(n) ⊆ B(λ(n)). Now let λ(n) = {ei1 , . . . , eiℓ } with ℓ ≤ k. Of course, if we restrict each eij to the subedge e′ij = eij ∩ χ(n) and define λ′ (n) = {e′i1 , . . . , e′iℓ }, then we get χ(n) = B(λ′ (n)). The key to the tractability shown in [Fischl et al., 2018] in case of the BIP (say, the intersection of any two distinct edges is bounded by a constant b) is that each e′ij is either equal to eij or a subset of eij with |e′ij | ≤ k · b. Hence, there are only polynomially many choices of subedges e′ij and also of χ(n). In [Fischl et al., 2019], this property was used to design a program for GHD computation as a straightforward extension of Det-K-Decomp by adding the relevant (polynomially many!) subedges.

In [Fischl et al., 2019], yet another GHD algorithm was presented. It is based on the use of balanced separators and extends ideas from [Akatov, 2010]. The motivation of this approach comes from the observation that there is no useful upper bound on the size of the subproblems that have to be solved by the recursive calls of the Det-K-Decomp algorithm. In fact, for some node n with corresponding component C and edge set E, let C1, . . . , Cℓ denote the [λ(n)]-components with Ci ⊆ C. Then there may exist an i such that Ei = {e | e ∩Ci ̸= ∅} is "almost" as big as E. In other words, in the worst case, the recursion depth of Det-K-Decomp may be linear in the number of edges.

The Balanced Separator approach from [Fischl et al., 2019] uses the fact that every GHD must contain a node whose λlabel is a balanced separator. Hence, in each recursive decomposition step for some subset EC of the edges of H, the algorithm "guesses" a node n′ such that λ(n′ ) is a balanced separator of the hypergraph with edges EC. Of course, this node n′ is not necessarily a child node ni of the current node n but may lie somewhere inside the subtree Ti below n. However, since GHDs can be arbitrarily rooted, one may first compute this subtree Ti with n′ as the root and with ni as a leaf node. This subtree is then (when returning from the recursion) connected to node n by rerooting Ti at ni and turning ni into a child node of n. The definition of balanced separators guarantees that the recursion depth is logarithmically bounded. This makes the Balanced Separator algorithm a good starting point for our parallel algorithm to be presented in Section 3.2.

3 Algorithmic Improvements &Parallelism

In this section, we first present a list of algorithmic improvements and then describe our strategy for designing parallel decomposition algorithms. Finally, we will show how to obtain a good hybrid strategy, which combines the strengths of the parallel and sequential approaches.

3.1 Algorithmic Improvements

Hypergraph preprocessing

An important consideration for speeding up decomposition algorithms is the simplification of the input hypergraph. Our considered reductions are:

· applying the GYO reduction from [Graham, 1979; Yu and ¨Ozsoyo˘glu, 1979], which repeatedly allows a) the removal of vertices occurring in a single edge, as well as b) edges contained in other edges. Note that the application of one rule may enable the application of the other rule, so their combination may lead to a greater simplification compared to just any one rule alone.

• the removal of all but one vertex out of a set of vertices of the same type. Here the type of a vertex v is defined as the set of edges e which contain v.

It is important to note that all these reductions neither add nor lose solutions. Formally, we get the following property:

Theorem 1 Preprocessing an input hypergraph by exhaustive application of the GYO reduction and the elimination of vertices of the same type as another vertex in the hypergraph, is sound and complete. More specifically, let H′ be the result of applying this preprocessing to a hypergraph H. Then, for any k ≥ 1, we have ghw(H′ ) ≤ k if and only if ghw(H) ≤ k. Moreover, any GHD of H′ can be efficiently transformed into a GHD of H of the same width.

Finding balanced separators fast

It has already been observed in [Gottlob and Samer, 2008] that the ordering in which edges are considered is vital for finding an appropriate edge cover λ(n) for the current node n in the decomposition fast. However, the ordering used in [Gottlob and Samer, 2008] for Det-K-Decomp, (which was called MCSO, i.e., maximal cardinality search ordering) turned out to be a poor fit for finding balanced separators. A natural alternative was to consider, for each edge e, all possible paths between vertices in the hypergraph H, and how much these paths increase after removal of e. This provides a weight for each edge, based on which we can define the maximal separator ordering. In our tests, this proved to be a very effective heuristic. Unfortunately, computing the maximal separator ordering requires solving the all-pairs shortest path problem. Using the well-known Floyd-Warshall algorithm [Floyd, 1962; Warshall, 1962] as a subroutine, this leads to a complexity of o(|E(H)| ∗ |V (H)|3 ), which is prohibitively expensive for practical instances. We thus explored two other, computationally simpler, heuristics, which order the edges in descending order of the following measures:

• The vertex degree of an edge e is defined as ∑v∈e deg(v), where deg(v) denotes the degree of a vertex v, i.e., the number of edges containing v.
• The edge degree of an edge e is |{f : e ∩ f}|, i.e., the number of edges e has a non-empty intersection with.

In our empirical evaluation, we found both of these to be useful compromises between speeding up the computation and complexity of computing the ordering itself, with the vertex degree ordering yielding the best results, i.e., compute λ(n) by first trying to select edges with higher vertex degree.

Reducing the search space

The GHD algorithm based on balanced separators presented in [Fischl et al., 2019] searches through all ℓ-tuples of edges (with ℓ ≤ k) to find the next balanced separator. The number of edge-combinations thus checked is ∑ki=1 (Ni ), where N denotes the number of edges. Note that this number of edges is actually higher than in the input hypergraph due to the subedges that have to be added for the tractability of GHD computation (see Section 2.2).

We can reduce this significantly by shifting our focus on the actual bags χ(n) generated from each λ(n) thus computed. Therefore, we initially only look for balanced separators of size k, checking (Nk ) many initial choices of λ(n). Only if a choice of λ(n) and χ(n) = ⋃ λ(n) does not lead to a successful recursive call of the decomposition procedure, we also inspect subsets of χ(n) - strictly avoiding the computation of the same subset of χ(n) several times by inspecting different subedges of the original edge cover λ(n). We thus also do not add subedges to the hypergraph upfront but only as they are needed as part of the backtracking when the original edge cover λ(n) did not succeed. Separators consisting of fewer edges are implicitly considered by allowing also the empty set as a possible subedge.

Summary. Our initial focus was to speed up existing decomposition algorithms via improvements as described above. However, even though these algorithmic improvements showed some positive effect, it turned out that a more fundamental change is needed. We thus turned our attention to parallelisation, which will be the topic of the next section.

3.2 Parallelisation Strategy

As described in more detail below, we use a divide and conquer method, based on the balanced separator approach. This method divides a hypergraph into smaller hypergraphs, called subcomponents. Our method proceeds to work on these subcomponents in parallel, with each round reducing the size of the hypergraphs (i.e., the number of edges in each subcomponent) to at most half their size. Thus after logarithmically many rounds, the method will have decomposed the entire hypergraph, if a decomposition of width K exists. For the computation we use the modern programming language Go [Donovan and Kernighan, 2015], which has a model of concurrency based on [Hoare, 1978].

In Go, a goroutine is a sequential process. Multiple goroutines may run concurrently. In the pseudocode provided, these are spawned using the keyword go, as can be seen in Algorithm 1, line 15. They communicate over channels. Using a channel ch is indicated by ← ch for receiving from a channel, and by ch ← for sending to ch.

Overview

Algorithm 1 contains the full decomposition procedure, whereas Algorithm 2 details the parallel search for separators, as it is a key subtask for parallelisation. To emphasise the core ideas of our parallel algorithm, we present it as a decision procedure, which takes as input a hypergraph H and a parameter K, and returns as output either Accept if ghw(H) ≤ K or Reject otherwise. Please note, however, that our actual implementation also produces a GHD of width ≤ K in case of an accepting run.

The parallel Balanced Separator algorithm begins with an initial call to the procedure Decomp, as seen in line 1 of Algorithm 1. The procedure Decomp takes two arguments, a hypergraphH′ for the current subcomponent considered, and a set Sp of "special edges". These special edges indicate the balanced separators encountered so far, as can be seen in line 15, where the current separator subSep is added to the argument on the recursive call, combining all its vertices into a new special edge. The special edges are needed to ensure that the decompositions of subcomponents can be combined to an overall decomposition, and are thus considered as additional edges. The recursive procedure Decomp has its base case in lines 3 to 4, when the size of H′ and Sp together is less than or equal to 2. The remainder of Decomp consists of two loops, the Separator Loop, from lines 6 to 23, which iterates over all balanced separators, and within it the SubEdge Loop, running from lines 11 to 22, which iterates over all subedge variants of any balanced separator. New balanced separators are produced with the subprocedure FindBalSep, used in line 7 of Algorithm 1, and detailed in Algorithm 2. After a separator is found, Decomp computes the new subcomponents in line 12. Then goroutines are started using recursive calls of Decomp for all found subcomponents. If any of these calls returns Reject, seen in line 18, then the procedure starts checking for subedges. If they have been exhausted, the procedure checks for another separator. If all balanced separators have been tried without success, then Decomp rejects in line 24.

We proceed to detail the parallelisation strategy of the two key subtasks: the search for new separators and the recursive calls over the subcomponents created from chosen separators.

Parallel search for balanced separators

For the search, while testing out a number of configurations, we settled ultimately on the following scenario, shown in Algorithm 2: The function FindBalSep first starts a number of Worker goroutines, seen in lines 3 to 4. These are also passed a channel, which they will use to send back any balanced separators they find. The worker procedure iterates over all candidate separators in its assigned search space, and sends back the first balanced separator it finds over the channel. Then FindBalSep waits for one of two conditions (whichever happens first): either one of the workers finds a balanced separator, lines 6 to 7, or none of them do and they all terminate on their own once they have exhausted the search space. Then the empty set is returned, as seen in line 8, indicating that no further balanced separators exist.

This design reduces the need for synchronisation: each worker is responsible for a share of the search space, and the only time a worker is stopped is when either it has found a separator which is balanced, or when another worker has done so. The number of worker goroutines scales with the number of available processors, thus allowing the search to optimally use the available resources. Our design addresses backtracking in this way: the workers employ a simple data structure, called Mi in Algorithm 2, to store their current progress, allowing them to generate the next separator to consider, and this data structure is stored in Decomp, seen in line 5 of Algorithm 1, even after the search is over. In case of backtracking, this allows to quickly continue the search exactly where it left of, without losing any work. If multiple workers find a balanced separator, one of them "wins", and during backtracking, the other workers can immediately send their found separators to FindBalSep again.

Parallel recursive calls.

For the recursive calls on subcomponents encountered, we create for each such call its own goroutine, as explained in the overview. This can be seen in Algorithm 1, line 15, where the output is then sent back via the channel ch. Given enough resources, this allows for each call to be run completely sep-

Input: H: Hypergraph Parameter: K: width parameter Output: Accept if ghw of H ≤ K, else Reject 1 return Decomp(H, ∅) ▷ initial call 2 function Decomp(H': Graph, Sp: Set of Special Edges) 3 if |H' ∪ Sp| ≤ 2 then ▷ Base Case 4 return Accept 5 M := a set of K-tuples 6 repeat ▷ Separator Loop 7 sep := FindBalSep(H', M) 8 if sep = ∅ then 9 break 10 subSep := sep 11 repeat ▷ SubeEge Loop 12 comp := getComponents(subSep, H', Sp) 13 ch := a channel 14 for c ∈ comp do 15 go ch ← Decomp(c.H, c.Sp ∪ ⋃ subSep) 16 while any recursive call still running do 17 out ← ch: ▷ Wait on channel 18 if out = Reject then 19 subSep = NextSubedgeSep(subSep) 20 continue SubEdge Loop 21 return Accept ▷ Found decomposition 22 until subSep = ∅ 23 until sep = ∅ 24 return Reject ▷ Exhausted Search Space

arately, thus easily fulfilling the need to minimise synchronisation. This fact - that all recursive calls can be worked on in parallel - is also in itself a major performance boost: in the sequential case we execute all recursive calls in a loop, but in the parallel case - see lines 14 to 15 in Algorithm 1 - we can execute these calls simultaneously. Thus, if one parallel call rejects, we can stop all the other calls early, and thus potentially save a lot of time. It is easy to imagine a case where in the sequential execution, a rejecting call is encountered only near the end of the loop.

It is important to note that this parallel algorithm is still a correct decomposition procedure. More formally, we state the following property:

Theorem 2 The algorithm for checking the ghw of a hypergraph given in Algorithm 1 is sound and complete. More specifically, Algorithm 1 with input H and parameter K will accept if and only if there exists a GHD of H with width ≤ K. Moreover, by materialising the decompositions implicitly constructed in the recursive calls of the DECOMP function, a GHD of width ≤ K can be constructed efficiently in case the algorithm returns Accept.

Based on this parallelisation scheme, we produced a parallel implementation of the Balanced Separator algorithm, with the improvements mentioned in Section 3.1. We already saw some promising results, but we noticed that for many in-

1 function FindBalSep(H': Graph, M: Set of K-tuples) 2 ch := a channel 3 for Mi ∈ M do 4 go WORKER(Mi, ch) 5 while any worker still running do 6 out ← ch: ▷ Wait on channel 7 return out 8 return empty set ▷ Exhausted Search Space 9 function Worker(Mi:K-tuple of integers,ch: Channel) 10 for sep ∈ NextSeparator(Mi) do 11 if IsBalanced(sep, H') then 12 ch ← sep ▷ Send sep to Master 13 return ▷ No separator found within Mi

stances, this purely parallel approach was not fast enough. We thus continued to explore a more nuanced approach, mixing both parallel and sequential algorithms.

3.3 Hybrid Approach - Best of BothWorlds

We now present a novel combination of parallel and sequential decomposition algorithms. It contains all the improvements mentioned in Section 3.1 and combines the Balanced Separator algorithm from Section 3.2 and Det-K-Decomp recalled in Section 2.1.

This combination is motivated by two observations: The Balanced Separator algorithm is very effective at splitting larger hypergraphs into smaller ones and in negative cases, where it can quickly stop the computation if no balanced separator for a given subcomponent exists. It is slower for smaller instances where the computational overhead to find balanced separators at every step slows things down. Furthermore, for technical reasons, it is also less effective at making use of caching. Det-K-Decomp, on the other hand, with proper heuristics, is very efficient for small instances and it allows for effective caching, thus avoiding repetition of work.

The Hybrid approach proceeds as follows: For a fixed number m of rounds, the algorithm tries to find balanced separators. Each such round is guaranteed to half the number of hyperedges considered. Hence, after those m rounds, the number of hyperedges in the remaining subcomponents will be reduced to at most |E(H)| 2m . The Hybrid algorithm then proceeds to finish the remaining subcomponents by using the Det-K-Decomp algorithm.

This required quite extensive changes to Det-K-Decomp, since it must be able to deal with Special Edges. Formally, each call of Det-K-Decomp runs sequentially. However, since the m rounds can produce a number of components, many calls of Det-K-Decomp can actually run in parallel. In other words, our Hybrid approach also brings a certain level of parallelism to Det-K-Decomp.

4 Experimental Evaluation and Results

We performed our experiments on the HyperBench benchmark, with the goal to determine the exact generalized hypertree width of all instances. We evaluated how our approach compares with existing attempts to compute the ghw, and we investigated how various heuristics and parameters prove beneficial for various instances. The detailed results of our experiments 1 , in addition to the source code of our Go programs 2 are publicly available. Together with the benchmark instances, which are detailed below and also publicly available, this ensures the reproducibility of our experiments.

4.1 Benchmark Instances and Setting

HyperBench. The instances used in our experiments are taken from the benchmark HyperBench, collated from various sources in industry and the literature, which was released by [Fischl et al., 2019] and made publicly available at http://hyperbench.dbai.tuwien.ac.at. It consists of 3071 hypergraphs from CQs and CSPs, where for many CSP instances the exact ghw was still undetermined.

Hardware and Software. We used Go 1.2 for our implementation, called BalancedGo. Our experiments ran on a cluster of 12 nodes, running Ubuntu 16.04.1 LTS with a 24 core Intel Xeon E5-2650v4 CPU, clocked at 2.20 GHz, each node with 160 GB of RAM. We disabled HyperThreading for the experiments.

Setup and Limits. For the experiments, we set a number of limits to test the efficiency of our solution. For each run, consisting of the input (i.e., hypergraph H and integer K) and a configuration of the decomposer, we set a one hour (3600 seconds) timeout and limit available RAM to 1 GB. These limits are justified by the fact that these are the exact same limits as were used in [Fischl et al., 2019], thus ensuring the direct comparability of our test results. To enforce these limits and run the experiments, we used the HTCondor software [Thain et al., 2005], originally named just Condor.

4.2 Results

The key results from our experiments are summarised in Table 1. Under "Decomposition Algorithms" we use (ensemble) to indicate that results from two algorithms are collected, i.e., results from the Hybrid algorithm and the parallel Balanced Separator algorithm. To also consider the performance of one of the individual approaches introduced in Section 3, namely the results of the Hybrid approach (from Section 3.3) is separately shown in a section of the table. As a reference point, we considered the NewDetK solver from [Fischl et al., 2019]. For each of these three, we also listed the average time and the maximal time to compute a GHD of optimal-width for each group of instances of HyperBench, as well as the standard deviation. The minimal times are left out for brevity, since they are always near or equal to 0. Note that for HyberBench the instance groups "CSP App." or "CQ App.", listed in Table 1, are hypergraphs of (resp.) CSP or CQ instances from real world applications.

Across all experiments, out of the 3071 instances in HyperBench, our implementation BalancedGo solved over 2300, as seen in Table 1. By "solved" we mean that the precise ghw could be determined in these cases. We observed that the number of 2320 solved instances exceeds the sum of the solved cases by the two individual implementations of Hybrid algorithm and parallel Balanced Separator. This is due to the fact that the "ensemble" combines results from all individual approaches. We mean with "combine" that we use information gained from runs of all possible algorithms. For a hypergraph H and a width k, an accepting run gives us an upper bound (since the optimal ghw(H) is then clearly ≤ k), and a rejecting run gives us a lower bound (since then we know that ghw(H) > k). By pooling multiple algorithms, we can combine these produced upper and lower bounds to compute the optimal width (when both bounds meet) for more instances than any one algorithm could determine on its own. We note that the results for NewDetK from (Fischl et al, 2019) are also such an "ensemble", combining the results of three different GHD algorithms. It turned out that parallel Balanced Separator is particularly well suited for deriving lower bounds (i.e., detecting "Reject"-cases), while the Hybrid algorithm is best for deriving upper bounds (i.e., detecting "Accept"-cases).

1 See: Raw data available under [Gottlob et al., 2020]

2 See: https://github.com/cem-okulmus/BalancedGo

For the computationally most challenging instances of HyperBench, those of ghw ≥ 3, this signifies an increase of over 70 % in solved instances when compared with [Fischl et al., 2019]. In addition, when considering the CSP instances from real world applications, we managed to solve 763 instances, almost doubling the number from NewDetK. In total, we now know the exact ghw of around 70% of all hypergraphs from CSP instances and the exact ghw of around 75% of all hypergraphs of HyperBench.

We stress that, in the first place, our data is not about time, but rather about the number of instances solved within reasonable time constraints. And here we provide an improvement for these practical CSP instances of near 100% on the current state of the art; no such improvements have been achieved by other techniques recently. It is also noteworthy, that the Hybrid algorithm alone solved 1730 total cases, thus beating the total for NewDetK in [Fischl et al., 2019], which, as mentioned, combines the results of three different GHD algorithms.

5 Conclusion and Outlook

We presented novel parallel algorithms in this paper, advancing the ability to compute GHDs of a significantly larger set of CSPs. This paves the way for more applications to use them to speed up the evaluation of CSP instances.

For immediate future work, we want to look at parallel approaches to compute plain Hypertree Decompositions (HDs), since the Balanced Separator approach does not directly translate to them. Another interesting goal is harnessing Go's excellent cloud computing capabilities to extend our results beyond the computation of GHDs to actually evaluating large real-life CSPs in the cloud.

Acknowledgments

This work was supported by the Austrian Science Fund (FWF):P30930-N35. Georg Gottlob is a Royal Society Research Professor and acknowledges support by the Royal Society for the present work in the context of the project "RAISON DATA" (Project reference: RP\R1\201074). Gottlob is, moreover, grateful to Cristina Zoltan for having suggested Go as an appropriate language for the parallelisation of computing hypertree decompositions.