Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound Lill, Jonas Petrova, Kalina H Weber, Simon ddc:510 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). Springer Nature 2025 info:eu-repo/semantics/article doc-type:article text http://purl.org/coar/resource_type/c_2df8fbb1 https://research-explorer.ista.ac.at/record/19603 https://research-explorer.ista.ac.at/download/19603/20957 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> eng info:eu-repo/semantics/altIdentifier/doi/10.1007/s00453-025-01306-y info:eu-repo/semantics/altIdentifier/issn/0178-4617 info:eu-repo/semantics/altIdentifier/e-issn/1432-0541 info:eu-repo/semantics/altIdentifier/wos/001463103800001 https://creativecommons.org/licenses/by/4.0/ info:eu-repo/semantics/openAccess