{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,9]],"date-time":"2025-05-09T08:10:09Z","timestamp":1746778209077,"version":"3.40.5"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2025,4,28]],"date-time":"2025-04-28T00:00:00Z","timestamp":1745798400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,4,28]],"date-time":"2025-04-28T00:00:00Z","timestamp":1745798400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100006502","name":"Defense Sciences Office, DARPA","doi-asserted-by":"publisher","award":["W911NF2010022"],"award-info":[{"award-number":["W911NF2010022"]}],"id":[{"id":"10.13039\/100006502","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000121","name":"Division of Mathematical Sciences","doi-asserted-by":"publisher","award":["DMS-2318790"],"award-info":[{"award-number":["DMS-2318790"]}],"id":[{"id":"10.13039\/100000121","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Given graph <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$G=(V,E)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>G<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>V<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>E<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> with vertex set <jats:italic>V<\/jats:italic> and edge set <jats:italic>E<\/jats:italic>, the max <jats:italic>k<\/jats:italic>-cut problem seeks to partition the vertex set <jats:italic>V<\/jats:italic> into at most <jats:italic>k<\/jats:italic> subsets that maximize the weight (number) of edges with endpoints in different parts. This paper proposes a graph folding procedure (i.e., a procedure that reduces the number of the vertices and edges of graph <jats:italic>G<\/jats:italic>) for the weighted max <jats:italic>k<\/jats:italic>-cut problem that may help reduce the problem\u2019s dimensionality. While our theoretical results hold for any <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$k \\ge 2$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>\u2265<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, our computational results show the effectiveness of the proposed preprocess <jats:italic>only<\/jats:italic> for <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$k=2$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> and on two sets of instances. Furthermore, we observe that the preprocess improves the performance of a MIP solver on a set of large-scale instances of the max cut problem.<\/jats:p>","DOI":"10.1007\/s11590-025-02199-0","type":"journal-article","created":{"date-parts":[[2025,4,28]],"date-time":"2025-04-28T19:51:51Z","timestamp":1745869911000},"page":"899-917","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A folding preprocess for the max k-cut problem"],"prefix":"10.1007","volume":"19","author":[{"given":"Ramin","family":"Fakhimi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7983-7262","authenticated-orcid":false,"given":"Hamidreza","family":"Validi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Illya V.","family":"Hicks","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tam\u00e1s","family":"Terlaky","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luis F.","family":"Zuluaga","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,4,28]]},"reference":[{"issue":"1","key":"2199_CR1","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/BF02523688","volume":"18","author":"A Frieze","year":"1997","unstructured":"Frieze, A., Jerrum, M.: Improved approximation algorithms for MAX $$k$$-CUT and MAX BISECTION. Algorithmica 18(1), 67\u201381 (1997). https:\/\/doi.org\/10.1007\/BF02523688","journal-title":"Algorithmica"},{"issue":"3","key":"2199_CR2","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"CH Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425\u2013440 (1991). https:\/\/doi.org\/10.1016\/0022-0000(91)90023-X","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"2199_CR3","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1287\/opre.14.1.52","volume":"14","author":"RC Carlson","year":"1966","unstructured":"Carlson, R.C., Nemhauser, G.L.: Scheduling to minimize interaction cost. Oper. Res. 14(1), 52\u201358 (1966). https:\/\/doi.org\/10.1287\/opre.14.1.52","journal-title":"Oper. Res."},{"key":"2199_CR4","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/3-540-47867-1_20","volume-title":"Integer Programming and Combinatorial Optimization","author":"A Eisenbl\u00e4tter","year":"2002","unstructured":"Eisenbl\u00e4tter, A.: The semidefinite relaxation of the $$k$$-partition polytope is strong. In: Cook, W.J., Schulz, A.S. (eds.) Integer Programming and Combinatorial Optimization, pp. 273\u2013290. Springer, Berlin, Heidelberg (2002)"},{"key":"2199_CR5","doi-asserted-by":"crossref","unstructured":"Lange, J.-H., Andres, B., Swoboda, P.: Combinatorial persistency criteria for multicut and max-cut. In: Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition, pp. 6093\u20136102 (2019)","DOI":"10.1109\/CVPR.2019.00625"},{"issue":"5","key":"2199_CR6","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1016\/j.dam.2005.05.022","volume":"154","author":"I M\u00e9ndez-D\u00edaz","year":"2006","unstructured":"M\u00e9ndez-D\u00edaz, I., Zabala, P.: A branch-and-cut algorithm for graph coloring. Discret. Appl. Math. 154(5), 826\u2013847 (2006). https:\/\/doi.org\/10.1016\/j.dam.2005.05.022","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"2199_CR7","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1007\/s10589-017-9967-9","volume":"69","author":"J Fairbrother","year":"2018","unstructured":"Fairbrother, J., Letchford, A.N., Briggs, K.: A two-level graph partitioning problem arising in mobile wireless communications. Comput. Optim. Appl. 69(3), 653\u2013676 (2018). https:\/\/doi.org\/10.1007\/s10589-017-9967-9","journal-title":"Comput. Optim. Appl."},{"key":"2199_CR8","doi-asserted-by":"crossref","unstructured":"Gross, J.L., Yellen, J., Zhang, P.: Handbook of graph theory (2013)","DOI":"10.1201\/b16132"},{"issue":"1\u20133","key":"2199_CR9","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/S0166-218X(03)00388-3","volume":"132","author":"G Alexe","year":"2003","unstructured":"Alexe, G., Hammer, P.L., Lozin, V.V., Werra, D.: Struction revisited. Discrete Appl. Math. 132(1\u20133), 27\u201346 (2003)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"2199_CR10","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1006\/jagm.2001.1186","volume":"41","author":"J Chen","year":"2001","unstructured":"Chen, J., Kanj, I.A., Jia, W.: Vertex cover: further observations and further improvements. J. Algorithms 41(2), 280\u2013301 (2001)","journal-title":"J. Algorithms"},{"key":"2199_CR11","unstructured":"Gurobi Optimization, LLC: Gurobi Optimizer Reference Manual (2022). https:\/\/gurobi.com\/"},{"issue":"1","key":"2199_CR12","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/s12532-019-00165-3","volume":"12","author":"G Wang","year":"2020","unstructured":"Wang, G., Hijazi, H.: Exploiting sparsity for the min $$k$$-partition problem. Math. Program. Comput. 12(1), 109\u2013130 (2020). https:\/\/doi.org\/10.1007\/s12532-019-00165-3","journal-title":"Math. Program. Comput."},{"key":"2199_CR13","unstructured":"Stabler\u00a0B, S.E., Bar-Gera,\u00a0H.: Hazmat network data. GitHub (2019). https:\/\/github.com\/bstabler\/"},{"key":"2199_CR14","unstructured":"STOM-Group: Hazmat network data. GitHub (2019). https:\/\/github.com\/STOM-Group\/Hazmat-Network-Data"},{"key":"2199_CR15","unstructured":"Salemi, H., Buchanan, A.: Implementation of solving the distance-based critical node problem. GitHub (2021). https:\/\/github.com\/halisalemi\/DCNP"}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-025-02199-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-025-02199-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-025-02199-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,9]],"date-time":"2025-05-09T07:36:49Z","timestamp":1746776209000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-025-02199-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,28]]},"references-count":15,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["2199"],"URL":"https:\/\/doi.org\/10.1007\/s11590-025-02199-0","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"type":"print","value":"1862-4472"},{"type":"electronic","value":"1862-4480"}],"subject":[],"published":{"date-parts":[[2025,4,28]]},"assertion":[{"value":"6 July 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 March 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 April 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":"Our data and code is available at\u00a0.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Data and code availability"}}]}}