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

Jonas Lill, Kalina Petrova, Simon Weber

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 vertic…