We study the boundary of tractability for the Max-Cut problem in graphs. Our main result shows that Max-Cut above the Edwards-Erd o 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 several times over the past 15 years. Our algorithm is asymptotically optimal, under the Exponential Time Hypothesis, and is strengthened by a polynomial-time computable kernel of polynomial size.
In a graph G=(V,E), a bisection (X,Y) is a partition of V into sets X and Y such that |X|=<|Y|=<|X|+1. The size of (X,Y) is the number of edges between X and Y. In the Max Bisection problem we are given a graph G=(V,E) and are required to find a bisection of maximum size. It is not hard to see that @?|E| 2@? is a tight lower bound on the maximum size of a bisection of G. We study parameterized complexity of the following parameterized problem called Max Bisection above Tight Lower Bound (Max-Bisec-ATLB): decide whether a graph G=(V,E) has a bisection of size at least @?|E| 2@?+k, where k is the parameter. We show that this parameterized problem has a kernel with O(k^2) vertices and O(k^3) edges, i.e., every instance of Max-Bisec-ATLB is equivalent to an instance of Max-Bisec-ATLB on a graph with at most O(k^2) vertices and O(k^3) edges. A bisection of a graph is a bipartition of its vertex set in which the number of vertices in the two parts differ by at most one, and the size of the bisection is the number of edges which go across the two parts. Every graph with m edges has a bisection of size at least ⌈m 2 ⌉, and this bound is sharp for infinitely many graphs. Therefore, Gutin and Yeo considered the parameterized complexity of deciding whether an input graph with m edges has a bisection of size at least ⌈m 2 ⌉+k, where k is the parameter. They showed fixed-parameter tractability of this problem, and gave a kernel with O(k2) vertices. Here, we improve the kernel size to O(k) vertices. Under the Exponential Time Hypothesis, this result is best possible up to constant factors.