Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turz\'ik Bound
<|reference_start|>Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turz\'ik Bound: MaxCut is a classical NP-complete problem and a crucial building block in many combinatorial algorithms. The famous Edwards-Erd\H{o}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\H{o}s bound. This was later improved by Etscheid and Mnich [Algorithmica, 2017] to run in parameterized linear time, i.e., $f(k)\cdot 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\H{o}s bound, we use the difference to the Poljak-Turz\'ik bound. The Poljak-Turz\'ik 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\'ik bound can be larger and thus yield a smaller parameter k. Our algorithm also runs in parameterized linear time, i.e., $f(k)\cdot O(m+n)$.<|reference_end|>
@article{lill2024linear-time,
    title={Linear-Time MaxCut in Multigraphs Parameterized Above the
  Poljak-Turz\'ik Bound},
    author={Jonas Lill, Kalina Petrova, Simon Weber},
    journal={arXiv preprint arXiv:2407.01071},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.01071},
    primaryClass={cs.DS cs.CC cs.DM}
}