{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T09:58:11Z","timestamp":1776333491113,"version":"3.51.2"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,8,26]],"date-time":"2025-08-26T00:00:00Z","timestamp":1756166400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,8,26]],"date-time":"2025-08-26T00:00:00Z","timestamp":1756166400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100008131","name":"Rheinische Friedrich-Wilhelms-Universit\u00e4t Bonn","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100008131","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2025,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We analyze integer programming formulations for determining the treewidth of a graph that are based on perfect elimination orderings. For the first time, we prove structural properties that explain their limitations in providing convenient lower bounds and show how the latter are constituted. Moreover, we investigate a flow metric approach that proved promising to achieve approximation guarantees for the pathwidth of a graph, and we show why these techniques cannot be carried over to improve the addressed treewidth formulations. In addition, we present two complementary formulations for treewidth that employ positional rather than relational variables. Via computational experiments, we provide an impression on the quality and proportionality of the lower bounds on the treewidth obtained with different relaxations of perfect elimination ordering formulations.<\/jats:p>","DOI":"10.1007\/s00236-025-00505-y","type":"journal-article","created":{"date-parts":[[2025,8,26]],"date-time":"2025-08-26T07:28:05Z","timestamp":1756193285000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On integer linear programs for treewidth based on perfect elimination orderings (extended version)"],"prefix":"10.1007","volume":"62","author":[{"given":"Sven","family":"Mallach","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,8,26]]},"reference":[{"issue":"2","key":"505_CR1","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a $$k$$-tree. SIAM Journal on Algebraic Discrete Methods 8(2), 277\u2013284 (1987). https:\/\/doi.org\/10.1137\/0608024","journal-title":"SIAM Journal on Algebraic Discrete Methods"},{"key":"505_CR2","doi-asserted-by":"publisher","unstructured":"Bannach, M., Berndt, S., Ehlers, T.: Jdrasil: A modular library for computing tree decompositions. In: Iliopoulos, C.S., Pissis, S.P., Puglisi, S.J., Raman, R. (eds.) 16th Intern. Symp. on Experimental Algorithms (SEA 2017). Leibniz Intern. Proceedings in Informatics (LIPIcs), vol. 75, pp. 28\u201312821. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2017). https:\/\/doi.org\/10.4230\/LIPIcs.SEA.2017.28","DOI":"10.4230\/LIPIcs.SEA.2017.28"},{"key":"505_CR3","doi-asserted-by":"publisher","unstructured":"Berg, J., J rvisalo, M.: SAT-based approaches to treewidth computation: An evaluation. In: 2014 IEEE 26th Intern. Conf. on Tools with Artificial Intelligence, pp. 328\u2013335. IEEE Computer Society, New York City, US (2014). https:\/\/doi.org\/10.1109\/ICTAI.2014.57","DOI":"10.1109\/ICTAI.2014.57"},{"issue":"3","key":"505_CR4","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1093\/comjnl\/bxm037","volume":"51","author":"HL Bodlaender","year":"2007","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Combinatorial optimization on graphs of bounded treewidth. The Computer Journal 51(3), 255 (2007). https:\/\/doi.org\/10.1093\/comjnl\/bxm037","journal-title":"The Computer Journal"},{"issue":"2","key":"505_CR5","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1006\/jagm.1996.0049","volume":"21","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L., Kloks, T.: Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms 21(2), 358\u2013402 (1996). https:\/\/doi.org\/10.1006\/jagm.1996.0049","journal-title":"J. Algorithms"},{"issue":"3","key":"505_CR6","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1007\/s00224-011-9312-0","volume":"50","author":"HL Bodlaender","year":"2012","unstructured":"Bodlaender, H.L., Fomin, F.V., Koster, A.M.C.A., Kratsch, D., Thilikos, D.M.: A note on exact algorithms for vertex ordering problems on graphs. Theory of Computing Systems 50(3), 420\u2013432 (2012). https:\/\/doi.org\/10.1007\/s00224-011-9312-0","journal-title":"Theory of Computing Systems"},{"key":"505_CR7","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Fomin, F.V., Koster, A.M.C.A., Kratsch, D., Thilikos, D.M.: On exact algorithms for treewidth. In: Azar, Y., Erlebach, T. (eds.) Algorithms - ESA 2006, pp. 672\u2013683. Springer, Berlin, Heidelberg (2006)","DOI":"10.1007\/11841036_60"},{"issue":"3","key":"505_CR8","doi-asserted-by":"publisher","first-page":"286","DOI":"10.1111\/j.1467-8640.2005.00274.x","volume":"21","author":"HL Bodlaender","year":"2005","unstructured":"Bodlaender, H.L., Koster, A.M.C.A., Eijkhof, Fvd: Pre-processing rules for triangulation of probabilistic networks. Comput. Intell. 21(3), 286\u2013305 (2005). https:\/\/doi.org\/10.1111\/j.1467-8640.2005.00274.x","journal-title":"Comput. Intell."},{"key":"505_CR9","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L.: Dynamic programming on graphs with bounded treewidth. In: Lepist\u00f6, T., Salomaa, A. (eds.) Proc. 15th Intern. Colloq. on Automata, Languages and Programming. LNCS, vol. 317, pp. 105\u2013118. Springer, Berlin, Heidelberg (1988). https:\/\/doi.org\/10.1007\/3-540-19488-6_110","DOI":"10.1007\/3-540-19488-6_110"},{"key":"505_CR10","doi-asserted-by":"crossref","unstructured":"Bornstein, C.F., Vempala, S.: Flow metrics. In: Rajsbaum, S. (ed.) LATIN 2002: Theoretical Informatics, pp. 516\u2013527. Springer, Berlin, Heidelberg (2002)","DOI":"10.1007\/3-540-45995-2_45"},{"key":"505_CR11","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/3-540-44436-X_10","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"M Charikar","year":"2000","unstructured":"Charikar, M.: Greedy approximation algorithms for finding dense components in a graph. In: Jansen, K., Khuller, S. (eds.) Approximation Algorithms for Combinatorial Optimization, pp. 84\u201395. Springer, Berlin, Heidelberg (2000)"},{"key":"505_CR12","unstructured":"Coudert, D.: A note on integer linear programming formulations for linear ordering problems on graphs. Research Report hal-01271838, INRIA ; I3S ; Universit\u00e9 Nice Sophia Antipolis ; CNRS (Feb 2016). https:\/\/inria.hal.science\/hal-01271838"},{"issue":"1","key":"505_CR13","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF02992776","volume":"25","author":"GA Dirac","year":"1961","unstructured":"Dirac, G.A.: On rigid circuit graphs. Abh. Math. Semin. Univ. Hambg. 25(1), 71\u201376 (1961). https:\/\/doi.org\/10.1007\/BF02992776","journal-title":"Abh. Math. Semin. Univ. Hambg."},{"key":"505_CR14","doi-asserted-by":"publisher","unstructured":"Dell, H., Husfeldt, T., Jansen, B.M.P., Kaski, P., Komusiewicz, C., Rosamond, F.A.: The first parameterized algorithms and computational experiments challenge. In: Guo, J., Hermelin, D. (eds.) 11th Intern. Symp. on Parameterized and Exact Computation (IPEC 2016). Leibniz Intern. Proceedings in Informatics (LIPIcs), vol. 63, pp. 30\u20131309. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2017). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2016.30. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2017\/6931","DOI":"10.4230\/LIPIcs.IPEC.2016.30"},{"key":"505_CR15","doi-asserted-by":"publisher","unstructured":"Dell, H., Komusiewicz, C., Talmon, N., Weller, M.: The PACE 2017 parameterized algorithms and computational experiments challenge: The second iteration. In: Lokshtanov, D., Nishimura, N. (eds.) 12th Intern. Symp. on Parameterized and Exact Computation (IPEC 2017). Leibniz Intern. Proceedings in Informatics (LIPIcs), vol. 89, pp. 30\u201313012. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2018). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2017.30. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2018\/8558","DOI":"10.4230\/LIPIcs.IPEC.2017.30"},{"issue":"12","key":"505_CR16","doi-asserted-by":"publisher","first-page":"3247","DOI":"10.1016\/j.cor.2012.04.017","volume":"39","author":"A Duarte","year":"2012","unstructured":"Duarte, A., Escudero, L.F., Mart\u00ed, R., Mladenovic, N., Pantrigo, J.J., S\u00e1nchez-Oro, J.: Variable neighborhood search for the vertex separation problem. Computers & Operations Res 39(12), 3247\u20133255 (2012). https:\/\/doi.org\/10.1016\/j.cor.2012.04.017","journal-title":"Computers & Operations Res"},{"key":"505_CR17","volume-title":"A y-formulation for the treewidth","author":"C Feremans","year":"2002","unstructured":"Feremans, C., Oswald, M., Reinelt, G.: A y-formulation for the treewidth. Heidelberg University, Germany, Preprint (2002)"},{"key":"505_CR18","unstructured":"Goldberg, A.V.: Finding a maximum density subgraph. Technical report, University of California, Berkeley, USA (1984)"},{"key":"505_CR19","volume-title":"Algorithmic graph theory and perfect graphs","author":"MC Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic graph theory and perfect graphs. Academic Press, New York (1980)"},{"key":"505_CR20","doi-asserted-by":"publisher","unstructured":"Grigoriev, A., Ensinck, J.C.L., Usotskaya, N.: Integer linear programming formulations for treewidth. Research Memorandum 030, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR) (2011). https:\/\/doi.org\/10.26481\/umamet.2011030","DOI":"10.26481\/umamet.2011030"},{"key":"505_CR21","doi-asserted-by":"publisher","unstructured":"Grigoriev, A.: Possible and impossible attempts to solve the treewidth problem via ILPs. In: Fomin, F.V., Kratsch, S., Leeuwen, E.J. (eds.) Treewidth, Kernels, and Algorithms: Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday, pp. 78\u201388. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-42071-0_7","DOI":"10.1007\/978-3-030-42071-0_7"},{"issue":"4","key":"505_CR22","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/BF00264496","volume":"16","author":"T Lengauer","year":"1981","unstructured":"Lengauer, T.: Black-white pebbles and graph separation. Acta Informatica 16(4), 465\u2013475 (1981). https:\/\/doi.org\/10.1007\/BF00264496","journal-title":"Acta Informatica"},{"key":"505_CR23","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/j.jda.2018.11.012","volume":"52","author":"S Mallach","year":"2018","unstructured":"Mallach, S.: Linear ordering based MIP formulations for the vertex separation or pathwidth problem. Journal of Discrete Algorithms 52, 156\u2013167 (2018). https:\/\/doi.org\/10.1016\/j.jda.2018.11.012","journal-title":"Journal of Discrete Algorithms"},{"key":"505_CR24","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16729-4","volume-title":"The Linear Ordering Problem","author":"R Mart\u00ed","year":"2011","unstructured":"Mart\u00ed, R., Reinelt, G.: The Linear Ordering Problem. Springer, Berlin, Heidelberg (2011)"},{"issue":"2","key":"505_CR25","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1016\/j.ejor.2007.02.004","volume":"186","author":"R Mart\u00ed","year":"2008","unstructured":"Mart\u00ed, R., Campos, V., Pi\u00f1ana, E.: A branch and bound algorithm for the matrix bandwidth minimization. Europ. J. Operational Res. 186(2), 513\u2013528 (2008). https:\/\/doi.org\/10.1016\/j.ejor.2007.02.004","journal-title":"Europ. J. Operational Res."},{"key":"505_CR26","doi-asserted-by":"publisher","unstructured":"Mallach, S.: On integer linear programs for treewidth based on perfect elimination orderings. In: Hsieh, S.-Y., Hung, L.-J., Lee, C.-W. (eds.) Combinatorial Algorithms. 34th International Workshop, IWOCA 2023, pp. 294\u2013306. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-34347-6_25","DOI":"10.1007\/978-3-031-34347-6_25"},{"issue":"3","key":"505_CR27","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7(3), 309\u2013322 (1986). https:\/\/doi.org\/10.1016\/0196-6774(86)90023-4","journal-title":"J. Algorithms"},{"key":"505_CR28","doi-asserted-by":"publisher","unstructured":"Tamaki, H.: Heuristic computation of exact treewidth. In: Schulz, C., U\u00e7ar, B. (eds.) 20th Intern. Symp. on Experimental Algorithms (SEA 2022). Leibniz Intern. Proceedings in Informatics (LIPIcs), vol. 233, pp. 17\u201311716. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2022). https:\/\/doi.org\/10.4230\/LIPIcs.SEA.2022.17","DOI":"10.4230\/LIPIcs.SEA.2022.17"},{"key":"505_CR29","doi-asserted-by":"publisher","unstructured":"Y\u00fcceoglu, B.: Branch-and-cut algorithms for graph problems. PhD thesis, Maastricht University (January 2015). https:\/\/doi.org\/10.26481\/dis.20150226by","DOI":"10.26481\/dis.20150226by"},{"key":"505_CR30","doi-asserted-by":"publisher","unstructured":"Usotskaya, N.: Exploiting geometric properties in combinatorial optimization = benutten van geometrische eigenschappen in combinatiorische optimalisatie. PhD thesis, Maastricht University, Netherlands (January 2011). https:\/\/doi.org\/10.26481\/dis.20111214nu","DOI":"10.26481\/dis.20111214nu"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-025-00505-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-025-00505-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-025-00505-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,22]],"date-time":"2025-09-22T06:26:05Z","timestamp":1758522365000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-025-00505-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,26]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["505"],"URL":"https:\/\/doi.org\/10.1007\/s00236-025-00505-y","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,8,26]]},"assertion":[{"value":"28 March 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 August 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 August 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"34"}}