Generalized hypertree decompositions: NP-hardness and tractable variants

ABSTRACT

The generalized hypertree width GHW(H) of a hypergraph H is a measure of its cyclicity. Classes of conjunctive queries or constraint satisfaction problems whose associated hypergraphs have bounded GHW are known to be solvable in polynomial time. However, it has been an open problem for several years if for a fixed constant k and input hypergraph H it can be determined in polynomial time whether GHW(H) ≤ k. Here, this problem is settled by proving that even for k = 3 the problem is already NP-hard. On the way to this result, another long standing open problem, originally raised by Goodman and Shmueli [1984] in the context of join optimization is solved. It is proven that determining whether a hypergraph H admits a tree projection with respect to a hypergraph G is NP-complete. Our intractability results on generalized hypertree width motivate further research on more restrictive tractable hypergraph decomposition methods that approximate generalized hypertree decomposition (GHD). We show that each such method is dominated by a tractable decomposition method definable through a function that associates a set of partial edges to a hypergraph. By using one particular such function, we define the new Component Hypertree Decomposition method, which is tractable and strictly more general than other approximations to GHD published so far.

REFERENCES

• 1: Abiteboul, S., Hull, R., and Vianu, V. 1995. Foundations of Databases. Addison-Wesley, Reading, MA.
• 2: Adler, I. 2004. Marshals, monotone marshals, and hypertree-width. J. Graph Theory 47, 4, 275--296.
• 3: Adler, I. 2006. Width functions for hypertree decompositions. Ph.D. dissertation. Albert-Ludwigs-Universität Freiburg, Freiburg, Germany.
• 4: Adler, I., Gottlob, G., and Grohe, M. 2005. Hypertree-width and related hypergraph invariants. In Proceedings of the 3rd European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB'05). DMTCS Proceedings Series, vol. AE. 5--10.
• 5: Arnborg, S. 1985. Efficient algorithms for combinatorial problems on graphs with bounded decomposability—A survey. BIT 25, 2--23.
• 6: Arnborg, S., Lagergren, J., and Seese, D. 1991. Easy problems for tree decomposable graphs. J. Algor. 12, 2 (Jun), 308--340.
• 7: Beeri, C., Fagin, R., Maier, D., and Yannakakis, M. 1983. On the desirability of acyclic database schemes. J. ACM 30, 3, 479--513.
• 8: Chandra, A. K., and Merlin, P. M. 1977. Optimal implementation of conjunctive queries in relational databases. In Proceedings of the ACM Symposium on Theory of Computing (STOC'77). ACM, New York, 77--90.
• 9: Chang, C.-L., and Lee, R. C.-T. 1973. Symbolic Logic and Mechanical Theorem Proving. Academic Press, Inc., Orlando, FL.
• 10: Chekuri, C., and Rajaraman, A. 2000. Conjunctive query containment revisited. Theoret. Comput. Sci. 239, 2, 211--229.
• 11: Cohen, D., Jeavons, P., and Gyssens, M. 2008. A unified theory of structural tractability for constraint satisfaction problems. J. Comput. Syst. Sci. 74, 5 (Aug.), 721--743.
• 12: Cohen, D. A., Jeavons, P., and Gyssens, M. 2005. A unified theory of structural tractability for constraint satisfaction and spread cut decomposition. In Proceedings of the 19th International Joint Conference on Artificial Intelligence. 72--77.
• 13: Courcelle, B. 1990. Graph rewriting: An algebraic and logic approach. In Handbook of Theoretical Computer Science, Volume B. Elsevier Science Publishers, Amsterdam, The Netherlands, 193--242.
• 14: Downey, R. G., and Fellows, M. R. 1999. Parameterized Complexity. Springer-Verlag, New York.
• 15: Flum, J., Frick, M., and Grohe, M. 2002. Query evaluation via tree-decompositions. J. ACM 49, 6, 716--752.
• 16: Flum, J., and Grohe, M. 2006. Parameterized Complexity Theory. Texts in Theoretical Computer Science. Springer-Verlag, Berlin, Germany.
• 17: Gavril, F. 1974. The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Comb. Theory Series B 16, 47--56.
• 18: Golumbic, M. C., Kaplan, H., and Shamir, R. 1995. Graph sandwich problems. J. Algor. 19, 449--473.
• 19: Golumbic, M. C., and Wassermann, A. 1998. Complexity and algorithms for graph and hypergraph sandwich problems. Graphs Combinat. 14, 223--239.
• 20: Goodman, N., and Shmueli, O. 1983. Syntactic characterization of tree database schemas. J. ACM 30, 4, 767--786.
• 21: Goodman, N., and Shmueli, O. 1984. The tree projection theorem and relational query processing. J. Comput. Syst. Sci. 28, 1, 60--79.
• 22: Gottlob, G., and Greco, G. 2007. On the complexity of combinatorial auctions: Structured item graphs and hypertree decomposition. In Proceedings of the 8th ACM Conference on Electronic Commerce. ACM, New York, 152--161.
• 23: Gottlob, G., Greco, G., Miklós, Z., Scarcello, F., and Schwentick, T. 2009. Graph Theory, Computational Intelligence and Thought. Essays Dedicated to Martin Charles Golumbic on the Occasion of His 60th Birthday. Lecture Notes in Computer Science, vol. 5420. Springer-Verlag, Berlin, Germany, Chapter Tree Projections: Game Characterization and Computational Aspects, 87--99.
• 24: Gottlob, G., Leone, N., and Scarcello, F. 2000. A comparison of structural CSP decomposition methods. Artif. Intell. 124, 2, 243--282.
• 25: Gottlob, G., Leone, N., and Scarcello, F. 2001. The complexity of acyclic conjunctive queries. J. ACM 48, 3, 431--498.
• 26: Gottlob, G., Leone, N., and Scarcello, F. 2002. Hypertree decompositions and tractable queries. J. Comput. Syst. Sci. (JCSS) 64, 3 (May), 579--627.
• 27: Gottlob, G., Leone, N., and Scarcello, F. 2003. Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width. J. Comput. Syst. Sci. (JCSS) 66, 4, 775--808.
• 28: Gottlob, G., Pichler, R., and Wei, F. 2006. Bounded treewidth as a key to tractability of knowledge representation and reasoning. In Proceedings of AAAI 2006. AAAI Press.
• 29: Greco, G., and Scarcello, F. 2008. Tree projections: Hypergraph games and minimality. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol. 5125, Springer-Verlag, Berlin, Germany, 736--747.
• 30: Grohe, M., and Marx, D. 2006. Constraint solving via fractional edge covers. In Proceedings of the ACM SIAM Symposium on Discrete Algorithms (SODA). ACM, New York, 289--298.
• 31: Kolaitis, P. G., and Vardi, M. Y. 2000. Conjunctive query containment and constraint satisfaction. J. Comput. Syst. Sci. 61, 302--332.
• 32: Lustig, A., and Shmueli, O. 1999. Acyclic hypergraph projections. J. Algor. 30, 2, 400--422.
• 33: Marx, D. 2009. Approximating fractional hypetree width. In Proceedings of the ACM SIAM Symposium on Discrete Algorithms (SODA'09). ACM, New York, 902--911.
• 34: Robertson, N., and Seymour, P. D. 1986. Graph minors. II. Algorithmic aspects of tree-width. J. Algor. 7, 309--322.
• 35: Saccà, D. 1985. Closures of database hypergraphs. J. ACM 32, 4 (Oct.), 774--803.
• 36: Sagiv, Y., and Shmueli, O. 1993. Solving queries by tree projections. ACM Trans. Datab. Syst. 18, 3, 487--511.
• 37: Scarcello, F., Greco, G., and Leone, N. 2004. Weighted hypertree decompositions and optimal query plans. In Proceedings of the 23rd ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. ACM, New York, 210--221.
• 38: Yannakakis, M. 1981. Algorithms for acyclic database schemes. In Proceedings of the International Coference on Very Large Data Bases (VLDB'81), 82--94.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases; Query processing

General Terms:
Algorithms, Theory

Keywords:
Conjunctive query, NP-complete, TreeProjection Problem, acyclic, hypergraph, hypertree decomposition, tractable