{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:31:55Z","timestamp":1750221115601,"version":"3.41.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2019,2,18]],"date-time":"2019-02-18T00:00:00Z","timestamp":1550448000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"DoCS Doctoral Programme in Computer Science and the Research Funds of the University of Helsinki"},{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"crossref","award":["251170 COIN, 276412, 284591, and 312662"],"award-info":[{"award-number":["251170 COIN, 276412, 284591, and 312662"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2019,12,17]]},"abstract":"<jats:p>The BT algorithm of Bouchitt\u00e9 and Todinca based on enumerating potential maximal cliques, originally proposed for the treewidth and minimum fill-in problems, yields improved exact exponential-time algorithms for various graph optimization problems related to optimal triangulations. While the BT algorithm has received significant attention in terms of theoretical analysis, less attention has been paid on engineering efficient implementations of the algorithm for different problems and thereby on empirical studies on its effectiveness in practice. In this work, we provide an experimental evaluation of an implementation of the BT algorithm, based on our second-place winning entry in the 2nd Parameterized Algorithms and Computational Experiments Challenge (PACE 2017), extended to several related graph problems: treewidth, minimum fill-in, generalized and fractional hypertreewidth, and the total table size problem. Instead of focusing on problem-specific optimization of BT for a particular problem, our focus in this work is on studying the applicability of BT more generally to a range of problems. Based on the results, we conclude that an efficient implementation of the BT algorithm yields an empirically competitive approach to each of the considered problems when compared to available implementations of alternative problem-specific algorithmic approaches.<\/jats:p>","DOI":"10.1145\/3301297","type":"journal-article","created":{"date-parts":[[2019,2,19]],"date-time":"2019-02-19T20:54:15Z","timestamp":1550609655000},"page":"1-19","source":"Crossref","is-referenced-by-count":6,"title":["Solving Graph Problems via Potential Maximal Cliques"],"prefix":"10.1145","volume":"24","author":[{"given":"Tuukka","family":"Korhonen","sequence":"first","affiliation":[{"name":"University of Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeremias","family":"Berg","sequence":"additional","affiliation":[{"name":"University of Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matti","family":"J\u00e4rvisalo","sequence":"additional","affiliation":[{"name":"University of Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,2,18]]},"reference":[{"volume-title":"Proc","author":"Alviano Mario","key":"e_1_2_1_1_1","unstructured":"Mario Alviano , Carmine Dodaro , and Francesco Ricca . 2015. A MaxSAT algorithm using cardinality constraints of bounded size . In Proc . AAAI. AAAI Press , 2677--2683. Mario Alviano, Carmine Dodaro, and Francesco Ricca. 2015. A MaxSAT algorithm using cardinality constraints of bounded size. In Proc. AAAI. AAAI Press, 2677--2683."},{"key":"e_1_2_1_2_1","unstructured":"Carlos Ans\u00f3tegui Fahiem Bacchus Matti J\u00e4rvisalo and Ruben Martins. 2017. MaxSAT Evaluation 2017. Retrieved from http:\/\/mse17.cs.helsinki.fi\/.  Carlos Ans\u00f3tegui Fahiem Bacchus Matti J\u00e4rvisalo and Ruben Martins. 2017. MaxSAT Evaluation 2017. Retrieved from http:\/\/mse17.cs.helsinki.fi\/."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICTAI.2014.57"},{"key":"e_1_2_1_4_1","volume-title":"Andr\u00e9 Augusto Cir\u00e9, and Arvind U. Raghunathan","author":"Bergman David","year":"2016","unstructured":"David Bergman , Carlos H. Cardonha , Andr\u00e9 Augusto Cir\u00e9, and Arvind U. Raghunathan . 2016 . On the minimum chordal completion polytope. CoRR abs\/1612.01966. Retrieved from http:\/\/arxiv.org\/abs\/1612.01966. David Bergman, Carlos H. Cardonha, Andr\u00e9 Augusto Cir\u00e9, and Arvind U. Raghunathan. 2016. On the minimum chordal completion polytope. CoRR abs\/1612.01966. Retrieved from http:\/\/arxiv.org\/abs\/1612.01966."},{"key":"e_1_2_1_5_1","volume-title":"Raghunathan","author":"Bergman David","year":"2015","unstructured":"David Bergman and Arvind U . Raghunathan . 2015 . A Benders approach to the minimum chordal completion problem. In Proc. CPAIOR (Lecture Notes in Computer Science), Vol. 9075 . Springer , 47--64. David Bergman and Arvind U. Raghunathan. 2015. A Benders approach to the minimum chordal completion problem. In Proc. CPAIOR (Lecture Notes in Computer Science), Vol. 9075. Springer, 47--64."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1084-3"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/647680.732171"},{"volume-title":"Nonserial Dynamic Programming","author":"Bertele Umberto","key":"e_1_2_1_8_1","unstructured":"Umberto Bertele and Francesco Brioschi . 1972. Nonserial Dynamic Programming . Academic Press, Inc. , Orlando, FL . Umberto Bertele and Francesco Brioschi. 1972. Nonserial Dynamic Programming. Academic Press, Inc., Orlando, FL."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30577-4_1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1056106.1704943"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2390176.2390188"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1009"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9421-1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.12.017"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799359683"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00007-X"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(90)90060-D"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39071-5_13"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(99)00059-4"},{"key":"e_1_2_1_21_1","volume-title":"Proc. IPEC (LIPIcs)","volume":"63","author":"Dell Holger","unstructured":"Holger Dell , Thore Husfeldt , Bart M. P. Jansen , Petteri Kaski , Christian Komusiewicz , and Frances A. Rosamond . 2016. The first parameterized algorithms and computational experiments challenge . In Proc. IPEC (LIPIcs) , Vol. 63 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 30:1--30:9. Holger Dell, Thore Husfeldt, Bart M. P. Jansen, Petteri Kaski, Christian Komusiewicz, and Frances A. Rosamond. 2016. The first parameterized algorithms and computational experiments challenge. In Proc. IPEC (LIPIcs), Vol. 63. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 30:1--30:9."},{"key":"e_1_2_1_22_1","volume-title":"The PACE 2017 parameterized algorithms and computational experiments challenge: The second iteration. In Proc. IPEC 2017 (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 30:1--30:12","author":"Dell Holger","year":"2018","unstructured":"Holger Dell , Christian Komusiewicz , Nimrod Talmon , and Mathias Weller . 2018 . The PACE 2017 parameterized algorithms and computational experiments challenge: The second iteration. In Proc. IPEC 2017 (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 30:1--30:12 . Holger Dell, Christian Komusiewicz, Nimrod Talmon, and Mathias Weller. 2018. The PACE 2017 parameterized algorithms and computational experiments challenge: The second iteration. In Proc. IPEC 2017 (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 30:1--30:12."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/050643350"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/140964801"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_18"},{"volume-title":"Proc","author":"Freuder Eugene C.","key":"e_1_2_1_26_1","unstructured":"Eugene C. Freuder . 1990. Complexity of K-tree structured constraint satisfaction problems . In Proc . AAAI. AAAI Press , 4--9. Eugene C. Freuder. 1990. Complexity of K-tree structured constraint satisfaction problems. In Proc. AAAI. AAAI Press, 4--9."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.03.013"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(74)90094-X"},{"volume-title":"Proc","author":"Gogate Vibhav","key":"e_1_2_1_30_1","unstructured":"Vibhav Gogate and Rina Dechter . 2004. A complete anytime algorithm for treewidth . In Proc . UAI. AUAI Press , 201--208. Vibhav Gogate and Rina Dechter. 2004. A complete anytime algorithm for treewidth. In Proc. UAI. AUAI Press, 201--208."},{"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\/1412228.1412229"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2636918"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-04921-2_34"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33122-0_8"},{"key":"e_1_2_1_36_1","unstructured":"IBM ILOG. 2017. CPLEX Optimizer 12.7.0. Retrieved from https:\/\/www.ibm.com\/analytics\/data-science\/prescriptive-analytics\/cplex-optimizer.  IBM ILOG. 2017. CPLEX Optimizer 12.7.0. Retrieved from https:\/\/www.ibm.com\/analytics\/data-science\/prescriptive-analytics\/cplex-optimizer."},{"key":"e_1_2_1_37_1","volume-title":"Jensen and Frank Jensen","author":"Finn","year":"1994","unstructured":"Finn V. Jensen and Frank Jensen . 1994 . Optimal junction trees. In Proc. UAI. Morgan Kaufmann Publishers Inc ., 360--366. Finn V. Jensen and Frank Jensen. 1994. Optimal junction trees. In Proc. UAI. Morgan Kaufmann Publishers Inc., 360--366."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791222171"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1988.tb01721.x"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijar.2016.09.012"},{"key":"e_1_2_1_42_1","unstructured":"A Makhorin. 2001. GLPK-the GNU Linear Programming Toolkit. Retrieved from https:\/\/www.gnu.org\/software\/glpk\/.  A Makhorin. 2001. GLPK-the GNU Linear Programming Toolkit. Retrieved from https:\/\/www.gnu.org\/software\/glpk\/."},{"volume-title":"Proc. SAT (Lecture Notes in Computer Science)","author":"Martins Ruben","key":"e_1_2_1_43_1","unstructured":"Ruben Martins , Vasco M. Manquinho , and In\u00eas Lynce . 2014. Open-WBO: A modular MaxSAT solver . In Proc. SAT (Lecture Notes in Computer Science) , Vol. 8561 . Springer , 438--445. Ruben Martins, Vasco M. Manquinho, and In\u00eas Lynce. 2014. Open-WBO: A modular MaxSAT solver. In Proc. SAT (Lecture Notes in Computer Science), Vol. 8561. Springer, 438--445."},{"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.1016\/j.ipl.2011.12.002"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798336073"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijar.2012.06.006"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(70)90282-9"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/0205021"},{"volume-title":"New heuristic methods for tree decompositions and generalized hypertree decompositions. Master\u2019s thesis","author":"Schafhauser Werner","key":"e_1_2_1_51_1","unstructured":"Werner Schafhauser . 2006. New heuristic methods for tree decompositions and generalized hypertree decompositions. Master\u2019s thesis . Vienna University of Technology . Werner Schafhauser. 2006. New heuristic methods for tree decompositions and generalized hypertree decompositions. Master\u2019s thesis. Vienna University of Technology."},{"key":"e_1_2_1_52_1","volume-title":"Proc. ESA (Leibniz International Proceedings in Informatics (LIPIcs))","volume":"87","author":"Tamaki Hisao","year":"2017","unstructured":"Hisao Tamaki . 2017 . Positive-instance driven dynamic programming for treewidth . In Proc. ESA (Leibniz International Proceedings in Informatics (LIPIcs)) , Vol. 87 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 68:1--68:13. Hisao Tamaki. 2017. Positive-instance driven dynamic programming for treewidth. In Proc. ESA (Leibniz International Proceedings in Informatics (LIPIcs)), Vol. 87. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 68:1--68:13."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(85)90051-2"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213035"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3301297","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3301297","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:02:04Z","timestamp":1750208524000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3301297"}},"subtitle":["An Experimental Evaluation of the Bouchitt\u00e9--Todinca Algorithm"],"short-title":[],"issued":{"date-parts":[[2019,2,18]]},"references-count":52,"alternative-id":["10.1145\/3301297"],"URL":"https:\/\/doi.org\/10.1145\/3301297","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2019,2,18]]}}}