Crowston, RobertRobertCrowstonJones, MarkMarkJonesMnich, MatthiasMatthiasMnich2019-12-122019-12-122015-07-12Algorithmica (2015)http://hdl.handle.net/11420/4054We 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 (m/2) + (n-1/4) + k in time 2 O(k) ⋅n 4 , or decides that no such cut exists. This answers a long-standing open question from parameterized complexity that has been posed a number of times over the past 15 years. Our algorithm has asymptotically optimal running time, under the Exponential Time Hypothesis, and is strengthened by a polynomial-time computable kernel of polynomial size.en1432-054120153734757Springer NatureAllgemeines, WissenschaftJournal Article10.1007/s00453-014-9870-z1112.3506Other