article published yes Jonas Lill author Kalina H Petrova author 554ff4e4-f325-11ee-b0c4-a10dbd523381 Simon Weber author MaKw department IST-BRIDGE: International postdoctoral program project MaxCut is a classical NP-complete problem and a crucial building block in many combinatorial algorithms. The famousEdwards-Erdös bound states that any connected graph on n vertices with m edges contains a cut of size at least m/2 + n−1/4 . Crowston, Jones and Mnich [Algorithmica, 2015] showed that the MaxCut problem on simple connected graphs admits an FPT algorithm, where the parameter k is the difference between the desired cut size c and the lower bound given by the Edwards-Erdös bound. This was later improved by Etscheid and Mnich [Algorithmica, 2017] to run in parameterized linear time, i.e., f (k) · O(m). We improve upon this result in two ways: Firstly, we extend the algorithm to work also for multigraphs (alternatively, graphs with positive integer weights). Secondly, we change the parameter; instead of the difference to the Edwards-Erdös bound, we use the difference to the Poljak-Turzík bound. The Poljak-Turzík bound states that any weighted graph G has a cut of weight at least w(G)/2 + wMSF (G)/4 , where w(G) denotes the total weight of G, and wMSF (G) denotes the weight of its minimum spanning forest. In connected simple graphs the two bounds are equivalent, but for multigraphs the Poljak-Turzík bound can be larger and thus yield a smaller parameter k. Our algorithm also runs in parameterized linear time, i.e., f (k) · O(m + n). https://research-explorer.ista.ac.at/download/19603/20957/2025_Algorithmica_Lill.pdf application/pdfno https://creativecommons.org/licenses/by/4.0/ Springer Nature2025 eng 0178-4617 1432-0541 00146310380000110.1007/s00453-025-01306-y 87983-1007 https://research-explorer.ista.ac.at/record/18758 Lill, J., Petrova, K. H., &#38; Weber, S. (2025). Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound. <i>Algorithmica</i>. Springer Nature. <a href="https://doi.org/10.1007/s00453-025-01306-y">https://doi.org/10.1007/s00453-025-01306-y</a> Lill, Jonas, et al. “Linear-Time MaxCut in Multigraphs Parameterized above the Poljak-Turzík Bound.” <i>Algorithmica</i>, vol. 87, Springer Nature, 2025, pp. 983–1007, doi:<a href="https://doi.org/10.1007/s00453-025-01306-y">10.1007/s00453-025-01306-y</a>. Lill J, Petrova KH, Weber S. 2025. Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound. Algorithmica. 87, 983–1007. Lill, Jonas, Kalina H Petrova, and Simon Weber. “Linear-Time MaxCut in Multigraphs Parameterized above the Poljak-Turzík Bound.” <i>Algorithmica</i>. Springer Nature, 2025. <a href="https://doi.org/10.1007/s00453-025-01306-y">https://doi.org/10.1007/s00453-025-01306-y</a>. J. Lill, K. H. Petrova, and S. Weber, “Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound,” <i>Algorithmica</i>, vol. 87. Springer Nature, pp. 983–1007, 2025. J. Lill, K.H. Petrova, S. Weber, Algorithmica 87 (2025) 983–1007. Lill J, Petrova KH, Weber S. Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound. <i>Algorithmica</i>. 2025;87:983-1007. doi:<a href="https://doi.org/10.1007/s00453-025-01306-y">10.1007/s00453-025-01306-y</a> 196032025-04-20T22:01:28Z2026-01-05T13:46:08Z