conference paper published yes Jonas Lill author Kalina H Petrova author 554ff4e4-f325-11ee-b0c4-a10dbd523381 Simon Weber author MaKw department IPEC: Symposium on Parameterized and Exact Computation IST-BRIDGE: International postdoctoral program project MaxCut is a classical NP-complete problem and a crucial building block in many combinatorial algorithms. The famous Edwards-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 size at least (w(G))/2+(w_MSF(G))/4, where w(G) denotes the total weight of G, and w_MSF(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/18758/18775/2024_LIPIcs_Lill.pdf application/pdfno https://creativecommons.org/licenses/by/4.0/ Schloss Dagstuhl - Leibniz-Zentrum für Informatik2024Egham, United Kingdom eng 1868-8969 9783959773539 2407.01071 00153485190000210.4230/LIPIcs.IPEC.2024.2 321 https://research-explorer.ista.ac.at/record/19603 J. Lill, K.H. Petrova, S. Weber, in:, 19th International Symposium on Parameterized and Exact Computation, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. J. Lill, K. H. Petrova, and S. Weber, “Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound,” in <i>19th International Symposium on Parameterized and Exact Computation</i>, Egham, United Kingdom, 2024, vol. 321. Lill J, Petrova KH, Weber S. Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound. In: <i>19th International Symposium on Parameterized and Exact Computation</i>. Vol 321. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href="https://doi.org/10.4230/LIPIcs.IPEC.2024.2">10.4230/LIPIcs.IPEC.2024.2</a> Lill, J., Petrova, K. H., &#38; Weber, S. (2024). Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound. In <i>19th International Symposium on Parameterized and Exact Computation</i> (Vol. 321). Egham, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.IPEC.2024.2">https://doi.org/10.4230/LIPIcs.IPEC.2024.2</a> Lill, Jonas, Kalina H Petrova, and Simon Weber. “Linear-Time MaxCut in Multigraphs Parameterized above the Poljak-Turzík Bound.” In <i>19th International Symposium on Parameterized and Exact Computation</i>, Vol. 321. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href="https://doi.org/10.4230/LIPIcs.IPEC.2024.2">https://doi.org/10.4230/LIPIcs.IPEC.2024.2</a>. Lill J, Petrova KH, Weber S. 2024. Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound. 19th International Symposium on Parameterized and Exact Computation. IPEC: Symposium on Parameterized and Exact Computation, LIPIcs, vol. 321, 2. Lill, Jonas, et al. “Linear-Time MaxCut in Multigraphs Parameterized above the Poljak-Turzík Bound.” <i>19th International Symposium on Parameterized and Exact Computation</i>, vol. 321, 2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href="https://doi.org/10.4230/LIPIcs.IPEC.2024.2">10.4230/LIPIcs.IPEC.2024.2</a>. 187582025-01-05T23:01:57Z2026-01-05T13:46:07Z