Hypertree-decomposition via Branch-decomposition Marko Samer Institute of Information Systems (DBAI), Vienna University of Technology, Austria samer@dbai.tuwien.ac.at rr r ¢ ¨r ¢ r r Abstract v1 r ¢ ¨ r prp p p p p p p p p ¢ ¨ ¨ = v2r r r fr f rr r r Hypertree-decomposition is the most general ap- fr r fr r proach in the literature for identifying tractable computation problems encoded as hypergraphs. Figure 1: Splitting a vertex We show how the heuristic branch-decomposition approach for ordinary graphs of [Cook and Sey- mour, 2003] can be used for the heuristic construc- 2002] for the formal definition of a hypertree-decomposition. tion of hypertree-decompositions. The width of a hypertree-decomposition (T, , ) is given by maxpvertices (T) |(p)|, and the hypertree-width of a hypergraph is the minimum width over all its hypertree- 1 Introduction decompositions. Many N P-complete problems (e.g., the constraint satisfac- A branch-decomposition of a hypergraph H is a tuple tion problem CSP, the homomorphism problem HOM, the (T, ), where T = (V , E ) is a tree having |edges (H)| leaves Boolean conjunctive query problem BCQ, etc.) can be de- and in which every non-leaf vertex has degree three, and is scribed by hypergraphs in a natural way. It was shown by a bijection from the set of leaves of T to edges (H). The order [Gottlob et al., 2002] that in analogy to tree-width of graphs, of an edge e E is the number of vertices v var (H) such hypertree-width of hypergraphs is an appropriate measure for that there are leaves l1 and l2 of T in different components the cyclicity and therefore the tractability of the correspond- of T when removing e with v (l1 ) (l2 ). The width ing computation problems. In particular, they have shown of a branch-decomposition (T, ) is the maximum order of that NP-complete problems become polynomially solvable the edges of T, and the branch-width of a hypergraph is the and even highly parallelizable when restricted to instances minimum width over all its branch-decompositions. with bounded hypertree-width. Moreover, it was shown by [Gottlob et al., 2000] that hypertree-decomposition and 3 The Branch-decomposition Heuristic the corresponding measure of hypertree-width generalizes all other tractability measures for hypergraphs in the literature. In this section, we summarize the basic steps of the heuris- Recent research focuses on heuristic approaches for fast tic branch-decomposition approach of [Cook and Seymour, hypertree-decomposition with small width. In this presenta- 2003]. Note that this approach was developed for ordinary tion, we show how the heuristic approach of [Cook and Sey- graphs. Its starting point is the construction of the initial data mour, 2003] for branch-decomposition (of ordinary graphs) structure which is a star as shown in Fig. 1. This is done in can be used for heuristic hypertree-decomposition. such a way that for each edge in the graph there exists exactly one edge in the star. This edge is then labeled with the set 2 Preliminaries of vertices of the corresponding edge in the graph (i.e., each edge is labeled with exactly two vertices). Afterwards, the A hypergraph H is a tuple (V , E ), where V is a set of vertices vertices of the star are successively split (cf. Fig. 1) accord- (variables) and E (V )\{} is a set of hyperedges. We ing to the decomposition rules below. In each step, the two define var (H) = V and edges (H) = E . A hypertree for a vertices v1 and v2 resulting from the splitting are connected hypergraph H is a triple (T, , ), where T = (V , E ) is a tree by a new edge which is labeled by the intersection of the set of and : V var (H) and : V edges (H) are labeling vertices labeling the edges incident with v1 and the set of ver- functions. tices labeling the edges incident with v2 . This process stops A hypertree-decomposition of a hypergraph H is a hyper- when all non-leaf vertices have degree three; the resulting tree tree (T, , ) for H satisfying four conditions. Due to space is then a branch-decomposition of the underlying graph. restrictions, we refer the interested reader to [Gottlob et al., The decomposition rules can be divided into two classes: (i) the application of "safe splits" and (ii) the application of This work was supported by the Austrian Science Fund (FWF) the Eigenvector heuristic [Alon, 1986]. Safe splits divide the project P17222-N04. Another approach we investigate is dual to the above one B 1 A 1 A B in the sense that we obtain a hypertree where the -labels are given and appropriate -labels have to be set. To this aim, 2 3 2 3 let us first introduce the dual hypergraph of a hypergraph C = 4 C 4 D E as exemplified in Fig. 2. The dual hypergraph is simply ob- D E tained by swapping the roles of hyperedges and vertices. Our 5 5 6 6 procedure is then to (i) construct a branch-decomposition of F F the dual hypergraph by using the above heuristic, (ii) trans- form this branch-decomposition into a tree-decomposition, Figure 2: A hypergraph and its dual hypergraph and (iii) interpret the labels of this tree-decomposition as - labels of a hypertree and set the -labels appropriately in a straight-forward way. The resulting hypertree is then a graph in such a way that it remains extendible, i.e., there is hypertree-decomposition of the original hypergraph. some way to (repeatedly) divide the subgraphs to obtain a The attentive reader may have noticed that there are two branch-decomposition of width equal to the branch-width of problems with the latter approach: First, the branch-width the original graph. In other words, nothing bad can happen and therefore also the hypertree-width is at least the cardinal- when applying safe splits. There are three kinds of safe splits ity of the largest edge in the dual hypergraph which is equal to presented by [Cook and Seymour, 2003]: (i) pushing, (ii) 2- the maximum number of hyperedges having a common vertex separations, and (iii) 3-separations. At each stage, these safe in the original hypergraph. Second, since the -labels satisfy splits are applied as long as possible. If none of them is ap- the conditions of a tree-decomposition by construction, the plicable, the Eigenvector heuristic is used. hypertree-width may be larger than necessary. However, by introducing heuristic pre- and post-processing steps, we are 4 Application to Hypertree-decomposition able to overcome both problems. We will now show how the branch-decomposition heuris- 5 Conclusion tic described in Section 3 can be used for hypertree- decomposition. Recall that this heuristic was developed for We have tested our approach on hypergraphs represent- ordinary graphs and not for hypergraphs. Thus, our first ing adder and bridge circuits connected in a line. For all step is to show that the safe splits as well as the Eigenvec- instances of such adder and bridge hypergraphs, we ob- tor heuristic are also applicable to hypergraphs. tained a hypertree-decomposition of almost optimal width To this aim, recall that the new edge introduced at each within a few seconds. Natural future work will be a full vertex splitting (cf. Fig. 1) is labeled with the intersection of implementation of our approach, the investigation of fur- two sets of vertices as described above. In general, however, ther improvements, and a systematic comparison with other this intersection may contain more than two vertices. Thus, hypertree-decomposition heuristics. Moreover, an implemen- such newly introduced edges represent hyperedges, i.e., the tation of our second approach in such a way that the tree- data structure underlying the original branch-decomposition decomposition of the dual hypergraph is directly constructed approach starts as an ordinary graph and evolves to a hyper- (e.g., by bucket elimination) without the intermediate-step of graph during the decomposition process. This can be seen as a branch-decomposition seems to be promising. an intuitive justification for the applicability of the branch- References decomposition heuristic to hypergraphs. It is easy to verify that this intuition holds indeed true. [Alon, 1986] N. Alon. Eigenvalues and expanders. Combi- Now, note that given a tree-decomposition1 of a hyper- natorica, 6(2):83­96, 1986. graph of width k , it is possible to construct a branch- [Cook and Seymour, 2003] W. Cook and P. Seymour. Tour decomposition of width at most k + 1, and given a branch- merging via branch-decomposition. INFORMS Journal on decomposition of a hypergraph of width k , it is possible Computing, 15(3):233­248, 2003. to construct a tree-decomposition of width at most 3k /2 [Gottlob et al., 2000] G. Gottlob, N. Leone, and F. Scarcello. [Robertson and Seymour, 1991]. Thus, having small tree- A comparison of structural CSP decomposition methods. width is equivalent to having small branch-width. Artificial Intelligence, 124(2):243­282, 2000. Hence, a simple approach to obtain a hypertree- decomposition via branch-decomposition is to (i) construct [Gottlob et al., 2002] G. Gottlob, N. Leone, and F. Scarcello. a branch-decomposition of the given hypergraph by using Hypertree decompositions and tractable queries. Journal the above heuristic, (ii) transform this branch-decomposition of Computer and System Sciences, 64(3):579­627, 2002. into a tree-decomposition, and, in analogy to [McMahan, [McMahan, 2004] B. McMahan. Bucket eliminiation and 2004], (iii) apply set covering heuristics in order to obtain hypertree decompositions. Implementation report, Insti- a hypertree-decomposition. In particular, set covering is used tute of Information Systems (DBAI), TU Vienna, 2004. to obtain appropriate -labels based on the -labels given by [Robertson and Seymour, 1991] N. Robertson and P. Sey- the tree-decomposition. mour. Graph minors. X. Obstructions to tree- 1 decomposition. Journal of Combinatorial Theory, Se- Intuitively, a tree-decomposition is a hypertree-decomposition ries B, 52:153­190, 1991. without the labeling function .