Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turzík Bound

MaxCut is a classical $\mathrm{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 $\frac{m}{2}+\frac{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\left(k\right)·O\left(m\right)$ . 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 $\frac{w\left(G\right)}{2}+\frac{w_{\mathrm{MSF}}\left(G\right)}{4}$ , where w(G) denotes the total weight of G, and $w_{\mathrm{MSF}}\left(G\right)$ 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\left(k\right)·O(m+n)$ .