A backtracking-based algorithm for hypertree decomposition

ABSTRACT

Hypertree decompositions of hypergraphs are a generalization of tree decompositions of graphs. The corresponding hypertree-width is a measure for the acyclicity and therefore an indicator for the tractability of the associated computation problem. Several NP-hard decision and computation problems are known to be tractable on instances whose structure is represented by hypergraphs of bounded hypertree-width. Roughly speaking, the smaller the hypertree-width, the faster the computation problem can be solved. In this paper, we present the new backtracking-based algorithm det-k-decomp for computing hypertree decompositions of small width. Our benchmark evaluations have shown that det-k-decomp significantly outperforms opt-k-decomp, the only exact hypertree decomposition algorithm so far. Even compared to the best heuristic algorithm, we obtained competitive results as long as the hypergraphs are sufficiently simple.

REFERENCES

• 1: Bodlaender, H. L. 2005. Discovering treewidth. In Proceedings of the 31st Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'05). Lecture Notes in Computer Science, vol. 3381. Springer-Verlag, New York. 1--16.
• 2: Dechter, R. 2003. Constraint Processing, Chapt. 4, Morgan Kaufmann, Burlington, MA. 85--115.
• 3: Ganzow, T., Gottlob, G., Musliu, N., and Samer, M. 2005. A CSP hypergraph library. Tech. Rept. DBAI-TR-2005-50, Institute of Information Systems (DBAI), TU Vienna.
• 4: Gottlob, G., Leone, N., and Scarcello, F. 1999. On tractable queries and constraints. In Proceedings of 10th International Conference on Database and Expert System Applications (DEXA). Lecture Notes in Computer Science, vol. 1677. Springer-Verlag, New York. 1--15.
• 5: Gottlob, G., Leone, N., and Scarcello, F. 2002. Hypertree decompositions and tractable queries. J. Comput. Syst. Sci. 64, 3, 579--627.
• 6: Gottlob, G., Leone, N., and Scarcello, F. 2003. Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width. J. Comput. Syst. Sci. 66, 4, 775--808.
• 7: Gottlob, G., Miklós, Z., and Schwentick, T. 2007. Generalized hypertree decompositions: NP-hardness and tractable variants. In Proceedings of the 26th ACM Symposium on Principles of Database Systems (PODS'07). ACM Press, New York. 13--22.
• 8: Harvey, P. and Ghose, A. 2003. Reducing redundancy in the hypertree decomposition scheme. In Proceedings of 15th International Conference on Tools with Artificial Intelligence (ICTAI'03). IEEE Computer Society, Los Alamitos, CA. 474--481.
• 9: Korimort, T. 2003. Constraint satisfaction problems—heuristic decomposition. Ph.D. thesis, Institute of Information Systems (DBAI), TU Vienna.
• 10: Koster, A. M. C. A., Bodlaender, H. L., and van Hoesel, S. P. M. 2001. Treewidth: Computational experiments. Tech. Rept. ZIB-Report 01-38, Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB).
• 11: Leone, N., Mazzitelli, A., and Scarcello, F. 2002. Cost-based query decompositions. In Proceedings of the 10th Italian Symposium on Advanced Database Systems (SEBD).
• 12: McMahan, B. 2004. Bucket elimination and hypertree decompositions. Implementation Rept. Institute of Information Systems (DBAI), TU Vienna.
• 13: Scarcello, F., Greco, G., and Leone, N. 2007. Weighted hypertree decompositions and optimal query plans. J. Comput. Syst. Sci. 73, 3, 475--506.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.2 Graph Theory
          Subjects: Trees; Hypergraphs

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods; Backtracking

General Terms:
Algorithms, Design, Experimentation

Keywords:
Constraint satisfaction, hypertree decomposition