Heuristic Hypertree Decomposition
Creators: name: Korimort, Thomas
Publisher: name: Zenodo
Year: 2003
Subjects: Computer Algorithm
High Complexity
NP
Heuristic Hypertree Decomposition
Hypergraphs
Constraint Satisfaction Problems
Database Theory
Heuristic Search

description: The problem of computing solutions to constraint satisfaction problems (CSPs) has gained widespread interest during the last few years, when resources became available to carry out significant computations on that topic. In the last few decades increasingly methods from database theory have been used in the area of constraint satisfaction. This is due to the fact that finite domain constraint satisfaction problems can be interpreted as databases. Different methods have been developed for improving the efficiency of the evaluation of questions concerning CSPs. Recently, a new method called hypertree decomposition has been developed by Gottlob and others, that dominates in a precise sense all known methods from the literature. However, computing an optimal decomposition of such a kind is very expensive in terms of space and time requirements. Thus the necessity arises for doing more than simply give an exact algorithm for computing optimal hypertree decompositions. This point is handled in detail in the present work. We develop a heuristics, that can compute good hypertree decompositions on hardware that is available at a low price. The space requirements of the algorithm are very modest compared to the exact algorithm for computing optimal hypertree decompositions. The time requirements can be adjusted and traded against the quality of the solution. The quality of the solution is compared in the environment of a constraint solver developed by DaimlerChrylser, which can import strategies generated from hypertree decompositions and use them for the evaluation of CSPs. Furthermore, correctness results about the heuristics containing a completely new type of inductive construction of hypertree decompositions are given as theoretical results together with a few applications of the concept of hypertree decomposition.
description: {"references": ["E.C. Freuder: A Sufficient Condition for Backtrack-Bounded Search. Journal of the ACM, Vol. 32, Number 4, pp. 755-761, October 1985.", "R. Fagin: Degrees of Acyclicity for Hypergraphs and Relational Database Schemes. Journal of the ACM, Vol. 30, Number 3, pp. 514-550, 1983.", "R.E. Tarjan, M. Yannakakis: Simple linear time algorithms to test chordality of graphs. SIAM Journal of Computing, Volume 13, Number 3, pp. 566-579, 1984.", "M.H. Graham: On the universal relation. Technical Report, University of Toronto, September 1979.", "C.T. Yu, M.Z. Ozsoyoglu: An algorithm for tree query membership of a distributed query. in Proceedings of IEEE COMPSAC, pp. 306-312, IEEE, New York, 1979.", "C. Beeri, R. Fagin, D. Maier, M. Yannakakis: On the desirability of acyclic database schemes. Journal of the ACM, Vol. 30, Number 3, pp. 479-513, 1983.", "G. Gottlob, N. Leone, F. Scarcello: Hypertree Decompositions and Tractable Queries. in Proceedings of PODS'99, Philadelphia, May 1999. Full version to appear in Journal of Computer and System Sciences. A preprint of the full version is currently stored in The Computer Research Repository, http://xxx.lanl.gov/archive/cs.", "G. Gottlob, N. Leone, F. Scarcello: A Comparison of Structural CSP Decomposition Methods. in Artificial Intelligence 124(2), pp. 243-282, 2000.", "N. Robertson, P.D. Seymour: Graph Minors II. Algorithmic aspects of tree width. Journal of Algorithms, Vol. 7, pp. 309-322, 1986.", "R. Dechter, J. Pearl: Tree clustering for constraint networks. Artificial Intelligence, Vol. 38, pp. 353-366, 1989.", "M. Gyssens, P.G. Jeavons, D.A. Cohen: Decomposing constraint satisfaction problems using database techniques. Artificial Intelligence 66, pp. 57-89, Elsevier, 1994.", "M. Gyssens, J. Paredaens: A Decomposition Methodology for Cyclic Databases. in Advances in Database Theory, Vol. 2, pp. 85-122, Plenum Press New York, NY, 1984.", "J. Mauss, F. Seelisch, M. Tatar: A Relational Constraint Solver for Model-based Engineering.", "G. Gottlob, N. Leone, F. Scarcello: Robbers, Marshals and Guards: Game Theoretic and Logical Characterizations of Hypertree Width, to appear in....", "M.R. Henzinger, S. Rao, H.N. Gabow: Computing vertex connectivity: new bounds from old techniques. in Proc. 37th IEEE F.O.C.S. (1996), pp. 462-471.", "A.H. Esfahanian: On the evolution of Graph Connectivity Algorithms.", "O. Reingold, S. Vadhan, A. Widgerson: Entropy Waves, The Zig-Zag Graph Product, and New Constant-Degree Expanders.", "V.V. Vazirani: Approximation Algorithms. Springer-Verlag, Berlin, 2001.", "Approximation Algorithms for NP-Hard Problems. Edited by D.S. Hochbaum. PWS Publishing Company, Boston MA, 1997.", "M. Hutle: Constraint Satisfaction Problems - Hybrid Decomposition and Evaluation. Vienna University of Technology, 2002.", "G. Gottlob, M. Hutle, S. Katzenbeisser, F. Wotawa: Computing Solutions to Heterogenous Constraint Networks Using Hypertree Decompositions. DBAI-TR-01-DC01, Vienna University of Technology, Vienna, June 2001."]}