Note on maximal bisection above tight lower bound
In a graph G = (V, E), a bisection (X, Y) is a partition of V into sets X and Y such that vertical bar X vertical bar <= vertical bar Y vertical bar <= vertical bar X vertical bar + 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 [vertical bar E vertical bar/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 [vertical bar E vertical bar/2] + k, where k is the parameter. We show that this parameterized problem has a kernel with 0(k(2)) vertices and 0(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 0(k2) vertices and 0(k3) edges. C) 2010 Elsevier B.V. All rights reserved.
kernels algorithms fixed-parameter tractability