{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T19:48:27Z","timestamp":1774986507900,"version":"3.50.1"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,17]]},"abstract":"<jats:p>\n                    Efficient query evaluation in databases and solving constraint satisfaction problems (CSPs) are crucial for improving performance in many real-world applications, from large-scale data management to decision-making systems. These problems naturally admit hypergraph representations, and are efficiently solvable using hypertree decomposition techniques, when the decomposition width is small. However, these techniques require finding small-width decompositions efficiently. This remains a significant challenge despite research from both the database and theory communities. In this work we present\n                    <jats:italic toggle=\"yes\">Ralph<\/jats:italic>\n                    <jats:italic toggle=\"yes\">(Randomized Approximation using Linear Programming for Hypertree-Decompositions),<\/jats:italic>\n                    a fast algorithm to compute low width fractional and generalized hypertree decompositions for input hypergraphs, as well as lower bounds for these widths. We build on the recent breakthrough by Korchemna et al. [FOCS 2024], which introduced the first polynomial time approximation algorithm for fractional (generalized) hypertree width. Our approach combines this theoretical advancement with practical heuristic improvements utilizing (mixed-integer) linear programs. Along the way, we present new algorithms with strong theoretical guarantees. Through empirical evaluation on the nearly 3700 instances of HyperBench, a well established benchmark suite for hypertree decompositions, we find near optimal decompositions for all previously solved instances and low width decompositions for all 500 previously unsolved instances, effectively pushing state-of-the-art.\n                  <\/jats:p>","DOI":"10.1145\/3725296","type":"journal-article","created":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:23:29Z","timestamp":1750281809000},"page":"1-27","source":"Crossref","is-referenced-by-count":0,"title":["Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3091-3823","authenticated-orcid":false,"given":"Vaishali","family":"Surianarayanan","sequence":"first","affiliation":[{"name":"University of California, Santa Barbara, Santa Barbara, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-3512-5181","authenticated-orcid":false,"given":"Anikait","family":"Mundhra","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara, Santa Barbara, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-4080-3647","authenticated-orcid":false,"given":"Ajaykrishnan","family":"E S","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara, Santa Barbara, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3166-9212","authenticated-orcid":false,"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara, Santa Barbara, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,18]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137765.3137791"},{"key":"e_1_2_2_2_1","first-page":"431","volume-title":"Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016","author":"Aberger Christopher R.","year":"2016","unstructured":"Christopher R. Aberger, Susan Tu, Kunle Olukotun, and Christopher R\u00e9. EmptyHeaded: A relational engine for graph processing. In Fatma \u00d6zcan, Georgia Koutrika, and Sam Madden, editors, Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016, San Francisco, CA, USA, June 26 - July 01, 2016, pages 431-446. ACM, 2016."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDEW.2016.7495625"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2007.04.013"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2022.12.025"},{"key":"e_1_2_2_6_1","first-page":"1","volume-title":"20th International Conference on Database Theory, ICDT 2017, March 21--24","volume":"68","author":"Afrati Foto N.","year":"2017","unstructured":"Foto N. Afrati, Manas R. Joglekar, Christopher R\u00e9, Semih Salihoglu, and Jeffrey D. Ullman. GYM: A multiround distributed join algorithm. In Michael Benedikt and Giorgio Orsi, editors, 20th International Conference on Database Theory, ICDT 2017, March 21--24, 2017, Venice, Italy, volume 68 of LIPIcs, pages 4:1-4:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2017."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742796"},{"key":"e_1_2_2_8_1","first-page":"1","volume-title":"23rd International Conference on Database Theory, ICDT 2020","volume":"155","author":"Chen Yu","year":"2020","unstructured":"Yu Chen and Ke Yi. Random sampling and size estimation over cyclic joins. In Carsten Lutz and Jean Christoph Jung, editors, 23rd International Conference on Database Theory, ICDT 2020, March 30-April 2, 2020, Copenhagen, Denmark, volume 155 of LIPIcs, pages 7:1-7:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2020."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/3510397.3510401"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-98334-9_8"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319683"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.13661"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508028.2505987"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902309"},{"key":"e_1_2_2_16_1","doi-asserted-by":"crossref","unstructured":"Georg Gottlob Martin Grohe Nysret Musliu Marko Samer and Francesco Scarcello. Hypertree decompositions: Structure algorithms and applications. In Dieter Kratsch editor Graph-Theoretic Concepts in Computer Science 31st International Workshop WG 2005 Metz France June 23--25 2005 Revised Selected Papers volume 3787 of Lecture Notes in Computer Science pages 1-15. Springer 2005.","DOI":"10.1007\/11604686_1"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3578266"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3638758"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3457374"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2023.114204"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1809"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10601-022-09332-1"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2636918"},{"key":"e_1_2_2_24_1","volume-title":"Gurobi Optimizer Reference Manual","author":"Optimization Gurobi","year":"2024","unstructured":"Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2016.02.024"},{"key":"e_1_2_2_26_1","volume-title":"Treetracker join: Turning the tide when a tuple fails to join. CoRR, abs\/2403.01631","author":"Hu Zeyuan","year":"2024","unstructured":"Zeyuan Hu and Daniel P. Miranker. Treetracker join: Turning the tide when a tuple fails to join. CoRR, abs\/2403.01631, 2024."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064027"},{"key":"e_1_2_2_28_1","article-title":"General dynamic yannakakis: conjunctive queries with theta joins under updates","volume":"619","author":"Idris Muhammad","year":"2020","unstructured":"Muhammad Idris, Mart\u00edn Ugarte, Stijn Vansummeren, Hannes Voigt, and Wolfgang Lehner. General dynamic yannakakis: conjunctive queries with theta joins under updates. VLDB J., 29(2--3):619-653, 2020.","journal-title":"VLDB J., 29(2--3)"},{"key":"e_1_2_2_29_1","volume-title":"Aggregations over generalized hypertree decompositions. CoRR, abs\/1508.07532","author":"Joglekar Manas","year":"2015","unstructured":"Manas Joglekar, Rohan Puttagunta, and Christopher R\u00e9. Aggregations over generalized hypertree decompositions. CoRR, abs\/1508.07532, 2015."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319694"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745776"},{"key":"e_1_2_2_32_1","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1145\/2902251.2902280","volume-title":"Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016","author":"Khamis Mahmoud Abo","year":"2016","unstructured":"Mahmoud Abo Khamis, Hung Q. Ngo, and Atri Rudra. FAQ: questions asked frequently. In Tova Milo and Wang-Chiew Tan, editors, Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016, pages 13-28. ACM, 2016."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3584372.3588676"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00053"},{"key":"e_1_2_2_35_1","unstructured":"Tuukka Korhonen. Finding optimal tree decompositions. PhD thesis Master's thesis University of Helsinki 2020. 2020."},{"key":"e_1_2_2_36_1","first-page":"1","volume-title":"41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024, March 12--14","volume":"289","author":"Lanzinger Matthias","year":"2024","unstructured":"Matthias Lanzinger and Igor Razgon. FPT approximation of generalised hypertree width for bounded intersection hypergraphs. In Olaf Beyersdorff, Mamadou Moustapha Kant\u00e9, Orna Kupferman, and Daniel Lokshtanov, editors, 41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024, March 12--14, 2024, Clermont-Ferrand, France, volume 289 of LIPIcs, pages 48:1-48:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2024."},{"key":"e_1_2_2_37_1","volume-title":"Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM (JACM), 46(6):787-832","author":"Leighton Tom","year":"1999","unstructured":"Tom Leighton and Satish Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM (JACM), 46(6):787-832, 1999."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721845"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.12.002"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196990"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180143"},{"issue":"1","key":"e_1_2_2_42_1","first-page":"65","article-title":"Graph minors. xiii. the disjoint paths problem. Journal of combinatorial theory","volume":"63","author":"Robertson Neil","year":"1995","unstructured":"Neil Robertson and Paul D Seymour. Graph minors. xiii. the disjoint paths problem. Journal of combinatorial theory, Series B, 63(1):65-110, 1995.","journal-title":"Series B"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976007.1"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2023.104015"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2764946"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/3579075.3579080"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3604437.3604450"},{"key":"e_1_2_2_48_1","first-page":"1969","volume-title":"SIGMOD '21: International Conference on Management of Data","author":"Wang Yilei","year":"2021","unstructured":"Yilei Wang and Ke Yi. Secure yannakakis: Join-aggregate queries over private data. In Guoliang Li, Zhanhuai Li, Stratos Idreos, and Divesh Srivastava, editors, SIGMOD '21: International Conference on Management of Data, Virtual Event, China, June 20--25, 2021, pages 1969-1981. ACM, 2021."},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735"},{"key":"e_1_2_2_50_1","volume-title":"7th International Conference, September 9--11, 1981","author":"Yannakakis Mihalis","year":"1981","unstructured":"Mihalis Yannakakis. Algorithms for acyclic database schemes. In Very Large Data Bases, 7th International Conference, September 9--11, 1981, Cannes, France, Proceedings, pages 82-94. IEEE Computer Society, 1981."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725296","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:51:58Z","timestamp":1774983118000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725296"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,17]]},"references-count":50,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,17]]}},"alternative-id":["10.1145\/3725296"],"URL":"https:\/\/doi.org\/10.1145\/3725296","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,17]]}}}