{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:16:29Z","timestamp":1778807789532,"version":"3.51.4"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2010,3,1]],"date-time":"2010-03-01T00:00:00Z","timestamp":1267401600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003549","name":"Orsz\u00e1gos Tudom\u00e1nyos Kutat\u00e1si Alapprogramok","doi-asserted-by":"publisher","award":["OTKA 67651"],"award-info":[{"award-number":["OTKA 67651"]}],"id":[{"id":"10.13039\/501100003549","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2010,3]]},"abstract":"<jats:p>\n            Fractional hypertree width is a hypergraph measure similar to tree width and hypertree width. Its algorithmic importance comes from the fact that, as shown in previous work, Constraint Satisfaction Problems (CSP) and various problems in database theory are polynomial-time solvable if the input contains a bounded-width fractional hypertree decomposition of the hypergraph of the constraints. In this article, we show that for every fixed\n            <jats:italic>w<\/jats:italic>\n            \u2265 1, there is a polynomial-time algorithm that, given a hypergraph\n            <jats:italic>H<\/jats:italic>\n            with fractional hypertree width at most\n            <jats:italic>w<\/jats:italic>\n            , computes a fractional hypertree decomposition of width\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>w<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            ) for\n            <jats:italic>H<\/jats:italic>\n            . This means that polynomial-time algorithms relying on bounded-width fractional hypertree decompositions no longer need to be given a decomposition explicitly in the input, since an appropriate decomposition can be computed in polynomial time. Therefore, if\n            <jats:italic>H<\/jats:italic>\n            is a class of hypergraphs with bounded fractional hypertree width, then a CSP restricted to instances whose structure is in\n            <jats:italic>H<\/jats:italic>\n            is polynomial-time solvable. This makes bounded fractional hypertree width the most general known hypergraph property that makes CSP, Boolean conjunctive queries, and conjunctive query containment polynomial-time solvable.\n          <\/jats:p>","DOI":"10.1145\/1721837.1721845","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":50,"title":["Approximating fractional hypertree width"],"prefix":"10.1145","volume":"6","author":[{"given":"D\u00e1niel","family":"Marx","sequence":"first","affiliation":[{"name":"Budapest University of Technology and Economics, Budapest, Hungary"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,4,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2007.04.013"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1009"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652168"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/788023.789067"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380868"},{"key":"e_1_2_1_7_1","unstructured":"Chen H. and Grohe M. 2006. Constraint satisfaction problems with succinctly specified relations. Manuscript. Preliminary version in Dagstuhl Seminar Proceedings 06401: Complexity of Constraints.  Chen H. and Grohe M. 2006. Constraint satisfaction problems with succinctly specified relations. Manuscript. Preliminary version in Dagstuhl Seminar Proceedings 06401: Complexity of Constraints."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(86)90019-1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_2_1_10_1","unstructured":"Flum J. and Grohe M. 2006. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer Berlin.   Flum J. and Grohe M. 2006. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer Berlin."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS'09)","author":"Fomin F. V."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the National Conference on Artificial Intelligence (AAAI-90)","author":"Freuder E. C.","year":"1990"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Golumbic M. C. 1980. Algorithmic Graph Theory and Perfect Graphs. Academic Press New York.   Golumbic M. C. 1980. Algorithmic Graph Theory and Perfect Graphs. Academic Press New York.","DOI":"10.1016\/B978-0-12-289260-8.50010-8"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11604686_1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1809"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265533"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm056"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11821069_5"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1206035.1206036"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109590"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380867"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263489"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1713"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90022-5"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1333875.1334193"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS'09)","author":"Marx D.","year":"2009"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0011-1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/11604686_5"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.06.006"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2005.10.006"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(85)90051-2"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Vazirani V. 2004. Approximation Algorithms. Springer.   Vazirani V. 2004. Approximation Algorithms. Springer.","DOI":"10.1007\/978-3-662-04565-7"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90072-7"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1721837.1721845","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1721837.1721845","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:23:38Z","timestamp":1750249418000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1721837.1721845"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,3]]}},"alternative-id":["10.1145\/1721837.1721845"],"URL":"https:\/\/doi.org\/10.1145\/1721837.1721845","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,3]]},"assertion":[{"value":"2008-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-04-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}