{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:15:52Z","timestamp":1778807752474,"version":"3.51.4"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2021,9,13]],"date-time":"2021-09-13T00:00:00Z","timestamp":1631491200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-sa\/4.0\/"}],"funder":[{"name":"Austrian Science Fund","award":["P30930 and Y698"],"award-info":[{"award-number":["P30930 and Y698"]}]},{"name":"Royal Society \u201cRAISON DATA\u201d","award":["RP\\R1\\201074"],"award-info":[{"award-number":["RP\\R1\\201074"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,10,31]]},"abstract":"<jats:p>\n            Hypertree decompositions (HDs), as well as the more powerful generalized hypertree decompositions (GHDs), and the yet more general fractional hypertree decompositions (FHDs) are hypergraph decomposition methods successfully used for answering conjunctive queries and for solving constraint satisfaction problems. Every hypergraph\n            <jats:italic>H<\/jats:italic>\n            has a width relative to each of these methods: its hypertree width\n            <jats:italic>hw(H)<\/jats:italic>\n            , its generalized hypertree width\n            <jats:italic>ghw(H)<\/jats:italic>\n            , and its fractional hypertree width\n            <jats:italic>fhw(H)<\/jats:italic>\n            , respectively. It is known that\n            <jats:italic>hw(H)\u2264 k<\/jats:italic>\n            can be checked in polynomial time for fixed\n            <jats:italic>k<\/jats:italic>\n            , while checking\n            <jats:italic>ghw(H)\u2264 k<\/jats:italic>\n            is NP-complete for\n            <jats:italic>k \u2265 3<\/jats:italic>\n            . The complexity of checking\n            <jats:italic>fhw(H)\u2264 k<\/jats:italic>\n            for a fixed\n            <jats:italic>k<\/jats:italic>\n            has been open for over a decade.\n          <\/jats:p>\n          <jats:p>\n            We settle this open problem by showing that checking\n            <jats:italic>fhw(H)\u2264 k<\/jats:italic>\n            is NP-complete, even for\n            <jats:italic>k=2<\/jats:italic>\n            . The same construction allows us to prove also the NP-completeness of checking\n            <jats:italic>ghw(H)\u2264 k<\/jats:italic>\n            for\n            <jats:italic>k=2<\/jats:italic>\n            . After that, we identify meaningful restrictions that make checking for bounded\n            <jats:italic>ghw<\/jats:italic>\n            or\n            <jats:italic>fhw<\/jats:italic>\n            tractable or allow for an efficient approximation of the\n            <jats:italic>fhw<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/3457374","type":"journal-article","created":{"date-parts":[[2021,9,13]],"date-time":"2021-09-13T23:44:10Z","timestamp":1631576650000},"page":"1-50","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Complexity Analysis of Generalized and Fractional Hypertree Decompositions"],"prefix":"10.1145","volume":"68","author":[{"given":"Georg","family":"Gottlob","sequence":"first","affiliation":[{"name":"University of Oxford, United Kingdom and TU Wien, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthias","family":"Lanzinger","sequence":"additional","affiliation":[{"name":"University of Oxford, United Kingdom and TU Wien, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Reinhard","family":"Pichler","sequence":"additional","affiliation":[{"name":"TU Wien, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Igor","family":"Razgon","sequence":"additional","affiliation":[{"name":"Birkbeck University of London, London, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,9,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915213"},{"key":"e_1_2_1_2_1","volume-title":"Old techniques for new join algorithms: A case study in RDF processing. CoRR abs\/1602.03557","author":"Aberger Christopher R.","year":"2016","unstructured":"Christopher R. Aberger , Susan Tu , Kunle Olukotun , and Christopher R\u00e9. 2016. Old techniques for new join algorithms: A case study in RDF processing. CoRR abs\/1602.03557 ( 2016 ). Christopher R. Aberger, Susan Tu, Kunle Olukotun, and Christopher R\u00e9. 2016. Old techniques for new join algorithms: A case study in RDF processing. CoRR abs\/1602.03557 (2016)."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1384252.1384253"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2007.04.013"},{"key":"e_1_2_1_5_1","volume-title":"Ullman","author":"Afrati Foto N.","year":"2017","unstructured":"Foto N. Afrati , Manas Joglekar , Christopher R\u00e9 , Semih Salihoglu , and Jeffrey D . Ullman . 2017 . GYM : A multiround join algorithm in MapReduce. In Proceedings of ICDT, Vol. 68 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik , 4:1\u20134:18. Foto N. Afrati, Manas Joglekar, Christopher R\u00e9, Semih Salihoglu, and Jeffrey D. Ullman. 2017. GYM: A multiround join algorithm in MapReduce. In Proceedings of ICDT, Vol. 68. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 4:1\u20134:18."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742796"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5802\/aif.938"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/110859440"},{"key":"e_1_2_1_9_1","volume-title":"Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties","author":"Ausiello Giorgio","unstructured":"Giorgio Ausiello . 1999. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties . Springer . Retrieved from http:\/\/www.worldcat.org\/oclc\/249492438. Giorgio Ausiello. 1999. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer. Retrieved from http:\/\/www.worldcat.org\/oclc\/249492438."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556579"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/3167892.3167895"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02570718"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00220-0"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11564751_15"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0401005"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.08.001"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/647489.727145"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(89)90037-4"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305948"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/233157.233184"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322390"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319683"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196962"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1865499.1865500"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01864160"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90076-X"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508028.2505987"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2017.11.005"},{"key":"e_1_2_1_30_1","first-page":"1","article-title":"Fractional covers of hypergraphs with bounded multi-intersection. In Proceedings of MFCS (Lecture Notes in Computer Science), Vol. 170","volume":"41","author":"Gottlob Georg","year":"2020","unstructured":"Georg Gottlob , Matthias Lanzinger , Reinhard Pichler , and Igor Razgon . 2020 . Fractional covers of hypergraphs with bounded multi-intersection. In Proceedings of MFCS (Lecture Notes in Computer Science), Vol. 170 . Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik , 41 : 1 \u2013 41 :14. Georg Gottlob, Matthias Lanzinger, Reinhard Pichler, and Igor Razgon. 2020. Fractional covers of hypergraphs with bounded multi-intersection. In Proceedings of MFCS (Lecture Notes in Computer Science), Vol. 170. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 41:1\u201341:14.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1809"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568320"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1206035.1206036"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109590"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2636918"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380867"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)90003-5"},{"key":"e_1_2_1_38_1","volume-title":"Advances in Data Base Theory","author":"Gyssens Marc","unstructured":"Marc Gyssens and Jan Paredaens . 1984. A decomposition methodology for cyclic databases . In Advances in Data Base Theory : Volume 2 . Springer , 85\u2013122. Marc Gyssens and Jan Paredaens. 1984. A decomposition methodology for cyclic databases. In Advances in Data Base Theory: Volume 2. Springer, 85\u2013122."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2016.02.024"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745776"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1713"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0965"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721845"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9248-9"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535926"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.12.002"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2656335"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(72)90019-2"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2764946"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-9977-x"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/500776"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/1286831.1286840"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3457374","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3457374","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:20Z","timestamp":1750191440000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3457374"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,13]]},"references-count":54,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,10,31]]}},"alternative-id":["10.1145\/3457374"],"URL":"https:\/\/doi.org\/10.1145\/3457374","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,13]]},"assertion":[{"value":"2018-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}