Max-Cut Parameterized Above the Edwards-Erd?s Bound
We study the boundary of tractability for the Max-Cut problem in graphs. Our main result shows that Max-Cut parameterized above the Edwards-Erd?s bound is fixed-parameter tractable: we give an algorithm that for any connected graph with n vertices and m edges finds a cut of size $$ \frac{m}{2} + \frac{n-1}{4} + k $$ in time 2 O(k)?n 4, or decides that no such cut exists.
fixed-parameter tractability algorithms and data structures maximum cuts combinatorial bounds