{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:18:31Z","timestamp":1778807911940,"version":"3.51.4"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,8,25]],"date-time":"2014-08-25T00:00:00Z","timestamp":1408924800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003549","name":"Orsz\u00e1gos Tudom\u00e1nyos Kutat\u00e1si Alapprogramok","doi-asserted-by":"publisher","award":["NK105645"],"award-info":[{"award-number":["NK105645"]}],"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":[[2014,10,28]]},"abstract":"<jats:p>Many important combinatorial problems can be modeled as constraint satisfaction problems. Hence, identifying polynomial-time solvable classes of constraint satisfaction problems has received a lot of attention. In this article, we are interested in structural properties that can make the problem tractable. So far, the largest structural class that is known to be polynomial-time solvable is the class of bounded hypertree width instances introduced by Gottlob et al. [2002]. Here we identify a new class of polynomial-time solvable instances: those having bounded fractional edge cover number. Combining hypertree width and fractional edge cover number, we then introduce the notion of fractional hypertree width. We prove that constraint satisfaction problems with bounded fractional hypertree width can be solved in polynomial time (provided that the tree decomposition is given in the input). Together with a recent approximation algorithm for finding such decompositions [Marx 2010], it follows that bounded fractional hypertree width is now the most generally known structural property that guarantees polynomial-time solvability.<\/jats:p>","DOI":"10.1145\/2636918","type":"journal-article","created":{"date-parts":[[2014,8,29]],"date-time":"2014-08-29T13:03:31Z","timestamp":1409317411000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":86,"title":["Constraint Solving via Fractional Edge Covers"],"prefix":"10.1145","volume":"11","author":[{"given":"Martin","family":"Grohe","sequence":"first","affiliation":[{"name":"RWTH Aachen University, Lehrstuhl f\u00fcr Informatik 7, Aachen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[{"name":"Institute for Computer Science and Control, Hungarian Academy of Sciences (MTA SZTAKI), Budapest, Hungary"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,8,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.v47:4"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2007.04.013"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"A. Atserias M. Grohe and D. Marx. 2013. Size bounds and query plans for relational joins. SIAM J. Comput. 42 (4) (2013) 1737--1767.  A. Atserias M. Grohe and D. Marx. 2013. Size bounds and query plans for relational joins. SIAM J. Comput. 42 (4) (2013) 1737--1767.","DOI":"10.1137\/110859440"},{"key":"e_1_2_1_5_1","unstructured":"C. Berge. 1976. Graphs and Hypergraphs. North Holland.   C. Berge. 1976. Graphs and Hypergraphs. North Holland."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120582.1120584"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970398.1970400"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.09.006"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380868"},{"key":"e_1_2_1_10_1","volume-title":"Lecture Notes in Computer Science","volume":"3709","author":"Chen H.","unstructured":"H. Chen and V. Dalmau . 2005. Beyond hypertree width: Decomposition methods without decompositions. In Principles and Practice of Constraint Programming (CP 2005), Peter van Beek (Ed.) . Lecture Notes in Computer Science , Vol. 3709 . Springer Berlin\/Heidelberg, 167--181. H. Chen and V. Dalmau. 2005. Beyond hypertree width: Decomposition methods without decompositions. In Principles and Practice of Constraint Programming (CP 2005), Peter van Beek (Ed.). Lecture Notes in Computer Science, Vol. 3709. Springer Berlin\/Heidelberg, 167--181."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.04.003"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(86)90019-1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.08.001"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming (CP\u201902)","author":"Dalmau V.","unstructured":"V. Dalmau , P. G. Kolaitis , and M. Y. Vardi . 2002. Constraint satisfaction, bounded treewidth, and finite-variable logics . In Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming (CP\u201902) . 310--326. V. Dalmau, P. G. Kolaitis, and M. Y. Vardi. 2002. Constraint satisfaction, bounded treewidth, and finite-variable logics. In Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming (CP\u201902). 310--326."},{"key":"e_1_2_1_15_1","unstructured":"R. Dechter. 2003. Constraint Processing. Morgan Kaufmann.   R. Dechter. 2003. Constraint Processing. Morgan Kaufmann."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(89)90037-4"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322390"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"F. V. Fomin P. A. Golovach and D. M. Thilikos. 2011. Approximating width parameters of hypergraphs with excluded minors. SIAM J. Discrete Math. 25 (3) (2011) 1331--1348.  F. V. Fomin P. A. Golovach and D. M. Thilikos. 2011. Approximating width parameters of hypergraphs with excluded minors. SIAM J. Discrete Math. 25 (3) (2011) 1331--1348.","DOI":"10.1137\/080743226"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 8th National Conference on Artificial Intelligence. 4--9.","author":"Freuder E. C.","year":"1990","unstructured":"E. C. Freuder . 1990 . Complexity of k-tree structured constraint satisfaction problems . In Proceedings of the 8th National Conference on Artificial Intelligence. 4--9. E. C. Freuder. 1990. Complexity of k-tree structured constraint satisfaction problems. In Proceedings of the 8th National Conference on Artificial Intelligence. 4--9."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02780332"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/11604686_1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2220357.2220363"},{"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.1006\/jcss.2001.1809"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00030-8"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568320"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1206035.1206036"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA\u201906)","author":"Grohe M.","unstructured":"M. Grohe and D. Marx . 2006. Constraint solving via fractional edge covers . In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA\u201906) . ACM, New York, 289--298. DOI: http:\/\/dx.doi.org\/10.1145\/1109557.1109590 10.1145\/1109557.1109590 M. Grohe and D. Marx. 2006. Constraint solving via fractional edge covers. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA\u201906). ACM, New York, 289--298. DOI: http:\/\/dx.doi.org\/10.1145\/1109557.1109590"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380867"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263489"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275511"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/060673898"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721845"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9248-9"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535926"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213565"},{"key":"e_1_2_1_39_1","volume-title":"Surveys in Combinatorics","author":"Reed B.","unstructured":"B. Reed . 1997. Tree width and tangles: A new connectivity measure and some applications . In Surveys in Combinatorics , R. A. Bailey (Ed.). LMS Lecture Note Series, Vol . 241. Cambridge University Press , 87--162. B. Reed. 1997. Tree width and tangles: A new connectivity measure and some applications. In Surveys in Combinatorics, R. A. Bailey (Ed.). LMS Lecture Note Series, Vol. 241. Cambridge University Press, 87--162."},{"key":"e_1_2_1_40_1","unstructured":"J.\n      Rhadakrishnan\n      . \n      Entropy\n       and \n      Counting\n    .\n   (\n  2003\n  ). Available at http:\/\/www.tcs.tifr.res.in\/&sim;jaikumar\/Papers\/EntropyAndCounting.pdf.  J. Rhadakrishnan. Entropy and Counting. (2003). Available at http:\/\/www.tcs.tifr.res.in\/&sim;jaikumar\/Papers\/EntropyAndCounting.pdf."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_2_1_42_1","volume-title":"Combinatorial Optimization. Polyhedra and Efficiency. Algorithms and Combinatorics","author":"Schrijver A.","unstructured":"A. Schrijver . 2003. Combinatorial Optimization. Polyhedra and Efficiency. Algorithms and Combinatorics , Vol. 24 . Springer , Berlin . A. Schrijver. 2003. Combinatorial Optimization. Polyhedra and Efficiency. Algorithms and Combinatorics, Vol. 24. Springer, Berlin."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1993.1027"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the 7th International Conference on Very Large Data Bases (VLDB\u201981)","author":"Yannakakis M.","year":"1981","unstructured":"M. Yannakakis . 1981 . Algorithms for acyclic database schemes . In Proceedings of the 7th International Conference on Very Large Data Bases (VLDB\u201981) . 82--94. M. Yannakakis. 1981. Algorithms for acyclic database schemes. In Proceedings of the 7th International Conference on Very Large Data Bases (VLDB\u201981). 82--94."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2636918","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2636918","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:19:22Z","timestamp":1750231162000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2636918"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8,25]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,10,28]]}},"alternative-id":["10.1145\/2636918"],"URL":"https:\/\/doi.org\/10.1145\/2636918","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,8,25]]},"assertion":[{"value":"2011-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-08-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}