{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:15:15Z","timestamp":1778807715158,"version":"3.51.4"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2009,9,1]],"date-time":"2009-09-01T00:00:00Z","timestamp":1251763200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/E010865\/1"],"award-info":[{"award-number":["EP\/E010865\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["P17222-N04"],"award-info":[{"award-number":["P17222-N04"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2009,9]]},"abstract":"<jats:p>\n            The generalized hypertree width GHW(\n            <jats:italic>H<\/jats:italic>\n            ) of a hypergraph\n            <jats:italic>H<\/jats:italic>\n            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\n            <jats:italic>k<\/jats:italic>\n            and input hypergraph\n            <jats:italic>H<\/jats:italic>\n            it can be determined in polynomial time whether GHW(\n            <jats:italic>H<\/jats:italic>\n            ) \u2264\n            <jats:italic>k<\/jats:italic>\n            . Here, this problem is settled by proving that even for\n            <jats:italic>k<\/jats:italic>\n            = 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\n            <jats:italic>H<\/jats:italic>\n            admits a tree projection with respect to a hypergraph\n            <jats:italic>G<\/jats:italic>\n            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.\n          <\/jats:p>","DOI":"10.1145\/1568318.1568320","type":"journal-article","created":{"date-parts":[[2009,9,8]],"date-time":"2009-09-08T12:53:03Z","timestamp":1252414383000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":67,"title":["Generalized hypertree decompositions: NP-hardness and tractable variants"],"prefix":"10.1145","volume":"56","author":[{"given":"Georg","family":"Gottlob","sequence":"first","affiliation":[{"name":"Oxford University, Parks Road, Oxford"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zolt\u00e1n","family":"Mikl\u00f3s","sequence":"additional","affiliation":[{"name":"\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Schwentick","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Dortmund, Dortmund, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,9,8]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley Reading MA.   Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley Reading MA."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.v47:4"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 3rd European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB'05)","volume":"10","author":"Adler I.","unstructured":"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 . 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."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/3765.3773"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90006-K"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322389"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_1_9_1","volume-title":"-T","author":"Chang C.-L.","year":"1973","unstructured":"Chang , C.-L. , and Lee , R. C . -T . 1973 . Symbolic Logic and Mechanical Theorem Proving. Academic Press , Inc., Orlando, FL. Chang, C.-L., and Lee, R. C.-T. 1973. Symbolic Logic and Mechanical Theorem Proving. Academic Press, Inc., Orlando, FL."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00220-0"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.08.001"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 19th International Joint Conference on Artificial Intelligence. 72--77","author":"Cohen D. A.","unstructured":"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 . 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."},{"key":"e_1_2_1_13_1","volume-title":"Handbook of Theoretical Computer Science","author":"Courcelle B.","unstructured":"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. 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."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Downey R. G. and Fellows M. R. 1999. Parameterized Complexity. Springer-Verlag New York.  Downey R. G. and Fellows M. R. 1999. Parameterized Complexity. Springer-Verlag New York.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/602220.602222"},{"key":"e_1_2_1_16_1","unstructured":"Flum J. and Grohe M. 2006. Parameterized Complexity Theory. Texts in Theoretical Computer Science. Springer-Verlag Berlin Germany.   Flum J. and Grohe M. 2006. Parameterized Complexity Theory. Texts in Theoretical Computer Science. Springer-Verlag Berlin Germany."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(74)90094-X"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1047"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s003730050028"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2157.322405"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90076-X"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250910.1250934"},{"key":"e_1_2_1_23_1","volume-title":"Lecture Notes in Computer Science","volume":"5420","author":"Gottlob G.","unstructured":"Gottlob , G. , Greco , G. , Mikl\u00f3s , 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. Gottlob, G., Greco, G., Mikl\u00f3s, 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."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(00)00078-3"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/382780.382783"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1809"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00030-8"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of AAAI","author":"Gottlob G.","year":"2006","unstructured":"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. 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."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_60"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109590"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1713"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0965"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496868"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4997"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/155271.155277"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055587"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the International Coference on Very Large Data Bases (VLDB'81)","author":"Yannakakis M.","year":"1981","unstructured":"Yannakakis , M. 1981 . Algorithms for acyclic database schemes . In Proceedings of the International Coference on Very Large Data Bases (VLDB'81) , 82--94. Yannakakis, M. 1981. Algorithms for acyclic database schemes. In Proceedings of the International Coference on Very Large Data Bases (VLDB'81), 82--94."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1568318.1568320","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1568318.1568320","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:38:49Z","timestamp":1750253929000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1568318.1568320"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9]]},"references-count":37,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2009,9]]}},"alternative-id":["10.1145\/1568318.1568320"],"URL":"https:\/\/doi.org\/10.1145\/1568318.1568320","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,9]]},"assertion":[{"value":"2007-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-09-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}