Hypertree

Complementary Approaches to Constraint Satisfaction

Home Members Publications Software downloads Work Progress

Work Progress 2004 2005 2006

2004 (01.10-31.12.2004)

We considered the development of initial algorithms for hypertree decompositions. We investigated hypertree-decomposition methods that operate directly on the hypergraph. In particular, at first we investigated algorithms for finding separator candidates, i.e., sets of hyperedges that divide a given hypergraph in such a way that a hypertree-decomposition of small width can be expected. Afterwards, we investigated measures for evaluating separators in order to select the best separator amongst the separator candidates. By recursively choosing such separators for each partition, we obtain a hypertree-decomposition of the given hypergraph. The better the separators are chosen, the smaller the resultig hypertee-width becomes. Our experience has shown that both problems (selecting separator candidates and evaluating separators) are combinatorial highly expensive and are only feasible when restricting the search space by the use of heuristics. First experimental results, however, have shown that such a direct approach leads only for small hypergraphs to good results. The results of this research were presented in Workshop on Graph and Hypergraph Decompositions-Methods and Applications in Computer Science (December 16-18, 2004, Vienna).

We started to collect benchmark examples from the literature and also considered generating hypergraphs based on their theoretical properties.

We performed research on how to apply hypertree decomposition in the context of data exchange.

We designed and implemented the basic data structures for an efficient implementation and evaluating hypertree-decomposition approaches which will be developed in future. Our implementation-framework is written in ANSI C++ and provides a series of useful subroutines that are often used in hypertree-decomposition algorithms.

Our group co-organized Workshop on Graph and Hypergraph Decompositions-Methods and Applications in Computer Science (December 16-18, 2004, Vienna). This workshop was directly connected to our research in this project and it brought together researchers in several fields (constraint satisfaction, databases, graph theory) to present and discuss more recent advances in the theory and application of graph and hypergraph decompositions, including Graph Decompositions, Hypertree Width, Hypergraphs and Queries, Clique Width, Matroids, and Applications of Decompositions Techniques in Databases, Constraint Satisfaction and other areas of interest.

 

2005:

We performed research on Quantified Constraint Satisfaction Problems and the use of structural decomposition methods to simplify such problems.

 

We extended our benchmark suite by further hypergraph examples.

 

We completed our implementation-framework used as basis for all our decomposition heuristics.

 

We reimplemented McMahans heuristic based on bucket elimination and set covering.

 

We investigated the application of the famous Eigenvector heuristic for hypertree decomposition.

 

We investigated the application of branch decomposition heuristics for hypertree decomposition.

 

We investigated hypertree decomposition based on the dual hypergraph.

 

We implemented all these approaches within our implementation framework.

 

We evaluated all these heuristics by our benchmark examples.

 

We automated experimental evaluations of implemented algorithms for the benchmark examples.

 

We developed and implemented a new exact algorithm for hypertree decomposition.

 

We investigated the use of hypergraph partitioning algorithms for hypertree decompositions. In this work we implemented and evaluated different hypergraph partitioning algorithms for generation of hypertree decompositions.

 

We investigated the combination of hypergraph partitioning algorithms and the tree decompositions based algorithms for hypertree decompositions.

 

We designed and implemented a new local search algorithm for the unicost set covering problem. This problem appears when the hypertree decompositions is generated from tree decompositions.

 

We designed and implemented a new general algorithm for the acyclic hypergraph sandwich problem. This general algorithm is used for generation of tree and hypertree decompositions.

 

We theoretically investigated the application of minimal cuts when using hypergraph partitioning heuristics for hypertree decomposition.

 

We investigated the complexity of generalized hypertree decomposition.

 

We have found a polynomial time algorithm for bounded dimension acyclic hypergraph sandwich problem.

 

We have found a new tractable class of CSP and compared it with the known tractable classes.

 

We organized a Mini-Workshop on Hypertree Decompositions.

 

 

2006:

We evaluated the exact algorithm for hypertree decompositions det-k-decomp on hypergraph library benchmarks.

 

We investigated the complexity and applications of edge-induced vertex-cuts.

 

Work about FPT of CSP, considering different parameters.

 

We investigated generalized hypertree decompositions and the properties of the subclasses of hypergraphs with bounded generalized hypertree width. We improved the definitions of the new tractable CSP subclass.

 

We analyzed the complexity of the decision problems for alpha-, beta-, and gamma-acyclic hypergraphs.

 

We developed and implemented an iterative heuristic algorithm for tree decompositions and evaluated it on dimacs instances.

 

We extended the iterative heuristic algorithm for tree decomposition to generate generalized hypertree decomposition.

 

We implemented a genetic algorithm (GA) and self adaptive GA for tree and generalized hypertree decompositions.

 

We implemented new branch and bound algorithms and proposed a new lower bound for generalized hypertree decompositions.

 

We implemented and evaluated an A* algorithms for tree and generalized hypertree decompositions.

We performed research on how to apply hypertree decomposition for shift scheduling problem.

We further improved the definitions of both the new tractable CSP subclass and beta-cover decomposition. We investigate their practical and theoretical applications.

 

 

 

2006 Database and Artificial Intelligence Group, Vienna University of Technology