{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:46:46Z","timestamp":1760240806498,"version":"build-2065373602"},"reference-count":52,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2019,9,20]],"date-time":"2019-09-20T00:00:00Z","timestamp":1568937600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We present an algorithm selection framework based on machine learning for the exact computation of treewidth, an intensively studied graph parameter that is NP-hard to compute. Specifically, we analyse the comparative performance of three state-of-the-art exact treewidth algorithms on a wide array of graphs and use this information to predict which of the algorithms, on a graph by graph basis, will compute the treewidth the quickest. Experimental results show that the proposed meta-algorithm outperforms existing methods on benchmark instances on all three performance metrics we use: in a nutshell, it computes treewidth faster than any single algorithm in isolation. We analyse our results to derive insights about graph feature importance and the strengths and weaknesses of the algorithms we used. Our results are further evidence of the advantages to be gained by strategically blending machine learning and combinatorial optimisation approaches within a hybrid algorithmic framework. The machine learning model we use is intentionally simple to emphasise that speedup can already be obtained without having to engage in the full complexities of machine learning engineering. We reflect on how future work could extend this simple but effective, proof-of-concept by deploying more sophisticated machine learning models.<\/jats:p>","DOI":"10.3390\/a12100200","type":"journal-article","created":{"date-parts":[[2019,9,20]],"date-time":"2019-09-20T10:48:14Z","timestamp":1568976494000},"page":"200","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A Machine Learning Approach to Algorithm Selection for Exact Computation of Treewidth"],"prefix":"10.3390","volume":"12","author":[{"given":"Borislav","family":"Slavchev","sequence":"first","affiliation":[{"name":"Department of Data Science and Knowledge Engineering, Maastricht University, 6211 LK Maastricht, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Evelina","family":"Masliankova","sequence":"additional","affiliation":[{"name":"Department of Data Science and Knowledge Engineering, Maastricht University, 6211 LK Maastricht, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9518-4724","authenticated-orcid":false,"given":"Steven","family":"Kelk","sequence":"additional","affiliation":[{"name":"Department of Data Science and Knowledge Engineering, Maastricht University, 6211 LK Maastricht, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,9,20]]},"reference":[{"key":"ref_1","unstructured":"Diestel, R. (2005). Graph Theory (Graduate Texts in Mathematics), Springer."},{"key":"ref_2","first-page":"1","article-title":"A tourist guide through treewidth","volume":"11","author":"Bodlaender","year":"1994","journal-title":"Acta Cybern."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1093\/comjnl\/bxm037","article-title":"Combinatorial optimization on graphs of bounded treewidth","volume":"51","author":"Bodlaender","year":"2008","journal-title":"Comput. J."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S. (2015). Parameterized Algorithms, Springer.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Bannach, M., and Berndt, S. (2019). Positive-Instance Driven Dynamic Programming for Graph Searching. arXiv.","DOI":"10.1007\/978-3-030-24766-9_4"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Hammer, S., Wang, W., Will, S., and Ponty, Y. (2019). Fixed-parameter tractable sampling for RNA design with multiple target structures. BMC Bioinform., 20.","DOI":"10.1186\/s12859-019-2784-7"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.disopt.2004.03.002","article-title":"Tree-width and the Sherali\u2013Adams operator","volume":"1","author":"Bienstock","year":"2004","journal-title":"Discret. Optim."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","article-title":"Complexity of finding embeddings in a k-tree","volume":"8","author":"Arnborg","year":"1987","journal-title":"SIAM J. Algeb. Discret. Methods"},{"key":"ref_9","unstructured":"Strasser, B. (2017). Computing Tree Decompositions with FlowCutter: PACE 2017 Submission. arXiv."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1016\/j.dam.2016.09.023","article-title":"ToTo: An open database for computation, storage and retrieval of tree decompositions","volume":"217","author":"Kelk","year":"2017","journal-title":"Discret. Appl. Math."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","article-title":"A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth","volume":"25","author":"Bodlaender","year":"1996","journal-title":"SIAM J. Comput."},{"key":"ref_12","first-page":"12","article-title":"On exact algorithms for treewidth","volume":"9","author":"Bodlaender","year":"2012","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"ref_13","unstructured":"Gogate, V., and Dechter, R. (2004, January 7\u201311). A complete anytime algorithm for treewidth. Proceedings of the 20th conference on Uncertainty in artificial intelligence, UAI 2004, Banff, AB, Canada."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1283","DOI":"10.1007\/s10878-018-0353-z","article-title":"Positive-instance driven dynamic programming for treewidth","volume":"37","author":"Tamaki","year":"2019","journal-title":"J. Comb. Optim."},{"key":"ref_15","unstructured":"Dell, H., Husfeldt, T., Jansen, B.M., Kaski, P., Komusiewicz, C., and Rosamond, F.A. (2016, January 24\u201326). The first parameterized algorithms and computational experiments challenge. Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC 2016), Aarhus, Denmark."},{"key":"ref_16","first-page":"1","article-title":"The PACE 2017 Parameterized Algorithms and Computational Experiments Challenge: The Second Iteration","volume":"Volume 89","author":"Lokshtanov","year":"2018","journal-title":"Proceedings of the 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), Leibniz International Proceedings in Informatics (LIPIcs)"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1126\/science.aaa8415","article-title":"Machine learning: Trends, perspectives, and prospects","volume":"349","author":"Jordan","year":"2015","journal-title":"Science"},{"key":"ref_18","unstructured":"Hutter, F., Hoos, H.H., and Leyton-Brown, K. (2019, January 4\u20137). Automated configuration of mixed integer programming solvers. Proceedings of the International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming, Thessaloniki, Greece."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Kruber, M., L\u00fcbbecke, M.E., and Parmentier, A. (2017, January 5\u20138). Learning when to use a decomposition. Proceedings of the International Conference on AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Padova, Italy.","DOI":"10.1007\/978-3-319-59776-8_16"},{"key":"ref_20","unstructured":"Tang, Y., Agrawal, S., and Faenza, Y. (2019). Reinforcement Learning for Integer Programming: Learning to Cut. arXiv."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"875","DOI":"10.1016\/j.cor.2011.07.006","article-title":"Measuring instance difficulty for combinatorial optimization problems","volume":"39","author":"Lopes","year":"2012","journal-title":"Comput. Oper. Res."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.artint.2013.10.003","article-title":"Algorithm runtime prediction: Methods & evaluation","volume":"206","author":"Hutter","year":"2014","journal-title":"Artif. Intell."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1145\/2594413.2594424","article-title":"Understanding the empirical hardness of NP-complete problems","volume":"57","author":"Hoos","year":"2014","journal-title":"Commun. ACM"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/s11750-017-0451-6","article-title":"On learning and branching: A survey","volume":"25","author":"Lodi","year":"2017","journal-title":"Top"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1287\/ijoc.2016.0723","article-title":"A machine learning-based approximation of strong branching","volume":"29","author":"Alvarez","year":"2017","journal-title":"INFORMS J. Comput."},{"key":"ref_26","unstructured":"Balcan, M.F., Dick, T., Sandholm, T., and Vitercik, E. (2018). Learning to branch. arXiv."},{"key":"ref_27","unstructured":"Bengio, Y., Lodi, A., and Prouvost, A. (2018). Machine Learning for Combinatorial Optimization: A Methodological Tour d\u2019Horizon. arXiv."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/j.cor.2018.04.006","article-title":"Machine learning meets mathematical optimization to predict the optimal production of offshore wind parks","volume":"106","author":"Fischetti","year":"2019","journal-title":"Comput. Oper. Res."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1016\/j.cor.2018.02.021","article-title":"Application of optimized machine learning techniques for prediction of occupational accidents","volume":"106","author":"Sarkar","year":"2019","journal-title":"Comput. Oper. Res."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"1547","DOI":"10.3233\/JIFS-169149","article-title":"Adaptive guided ejection search for pickup and delivery with time windows","volume":"32","author":"Nalepa","year":"2017","journal-title":"J. Intell. Fuzzy Syst."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/S0065-2458(08)60520-3","article-title":"The algorithm selection problem","volume":"Volume 15","author":"Rice","year":"1976","journal-title":"Advances in Computers"},{"key":"ref_32","unstructured":"Leyton-Brown, K., Nudelman, E., Andrew, G., McFadden, J., and Shoham, Y. (2003, January 9\u201315). A portfolio approach to algorithm selection. Proceedings of the IJCAI, Acapulco, Mexico."},{"key":"ref_33","unstructured":"Nudelman, E., Leyton-Brown, K., Devkar, A., Shoham, Y., and Hoos, H. (2019, July 12). Satzilla: An algorithm portfolio for SAT. Available online: http:\/\/www.cs.ubc.ca\/~kevinlb\/pub.php?u=SATzilla04.pdf."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1613\/jair.2490","article-title":"SATzilla: Portfolio-based algorithm selection for SAT","volume":"32","author":"Xu","year":"2008","journal-title":"J. Artif. Intell. Res."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/j.asoc.2004.12.002","article-title":"On learning algorithm selection for classification","volume":"6","author":"Ali","year":"2006","journal-title":"Appl. Soft Comput."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/s10479-007-0229-6","article-title":"A machine learning approach to algorithm selection for NP-hard optimization problems: A case study on the MPE problem","volume":"156","author":"Guo","year":"2007","journal-title":"Ann. Oper. Res."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Musliu, N., and Schwengerer, M. (2013, January 7\u201311). Algorithm selection for the graph coloring problem. Proceedings of the International Conference on Learning and Intelligent Optimization 2013 (LION 2013), Catania, Italy.","DOI":"10.1007\/978-3-642-44973-4_42"},{"key":"ref_38","unstructured":"Xu, L., Hutter, F., Hoos, H.H., and Leyton-Brown, K. (2011, January 16\u201320). Hydra-MIP: Automated algorithm configuration and selection for mixed integer programming. Proceedings of the RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion at the International Joint Conference on Artificial Intelligence (IJCAI), Paris, France."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1162\/evco_a_00242","article-title":"Automated algorithm selection: Survey and perspectives","volume":"27","author":"Kerschke","year":"2019","journal-title":"Evol. Comput."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"829","DOI":"10.1613\/jair.5312","article-title":"Improving the efficiency of dynamic programming on tree decompositions via machine learning","volume":"58","author":"Abseher","year":"2017","journal-title":"J. Artif. Intell. Res."},{"key":"ref_41","unstructured":"Bannach, M., Berndt, S., and Ehlers, T. (2017, January 21\u201323). Jdrasil: A modular library for computing tree decompositions. Proceedings of the 16th International Symposium on Experimental Algorithms (SEA 2017), London, UK."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/s10462-011-9272-4","article-title":"Decision trees: A recent overview","volume":"39","author":"Kotsiantis","year":"2013","journal-title":"Artif. Intell. Rev."},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Li, R.H., and Belford, G.G. (2002, January 23\u201326). Instability of decision tree classification algorithms. Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Edmonton, AB, Canada.","DOI":"10.1145\/775047.775131"},{"key":"ref_44","first-page":"18","article-title":"Classification and regression by randomForest","volume":"2","author":"Liaw","year":"2002","journal-title":"R News"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"1039","DOI":"10.1007\/s10994-017-5633-9","article-title":"Optimal classification trees","volume":"106","author":"Bertsimas","year":"2017","journal-title":"Mach. Learn."},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Cristianini, N., and Shawe-Taylor, J. (2000). An Introduction to Support Vector Machines and Other Kernel-Based Learning Methods, Cambridge University Press.","DOI":"10.1017\/CBO9780511801389"},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"1261","DOI":"10.1137\/070710275","article-title":"Divide-and-conquer approximation algorithm for vertex cover","volume":"23","author":"Stein","year":"2009","journal-title":"SIAM J. Discret. Math."},{"key":"ref_48","first-page":"2825","article-title":"Scikit-learn: Machine learning in Python","volume":"12","author":"Pedregosa","year":"2011","journal-title":"J. Mach. Learn. Res."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"1540023","DOI":"10.1142\/S0218213015400230","article-title":"Performance-estimation properties of cross-validation-based protocols with simultaneous hyper-parameter optimization","volume":"24","author":"Tsamardinos","year":"2015","journal-title":"Int. J. Artif. Intell. Tools"},{"key":"ref_50","first-page":"6","article-title":"Cross-disciplinary perspectives on meta-learning for algorithm selection","volume":"41","year":"2009","journal-title":"ACM Comput. Surv. (CSUR)"},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"2108","DOI":"10.1137\/120903518","article-title":"Preprocessing for treewidth: A combinatorial analysis through kernelization","volume":"27","author":"Bodlaender","year":"2013","journal-title":"SIAM J. Discret. Math."},{"key":"ref_52","unstructured":"Van Der Zanden, T.C., and Bodlaender, H.L. (2017). Computing Treewidth on the GPU. arXiv."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/10\/200\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:22:10Z","timestamp":1760188930000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/10\/200"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,20]]},"references-count":52,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2019,10]]}},"alternative-id":["a12100200"],"URL":"https:\/\/doi.org\/10.3390\/a12100200","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2019,9,20]]}}}