Minimum Bisection is fixed parameter tractable

Original · EN

In the classic Minimum Bisection problem we are given as input a graph G and an integer k. The task is to determine whether there is a partition of V(G) into two parts A and B such that ||A|-|B|| ≤ 1 and there are at most k edges with one endpoint in A and the other in B. In this paper we give an algorithm for Minimum Bisection with running time O(2ᵒ⁽ᵏ³⁾n³ ³ n). This is the first fixed parameter tractable algorithm for Minimum Bisection. At the core of our algorithm lies a new decomposition theorem that states that every graph G can be decomposed by small separators into parts where each part is "highly connected" in the following sense: any cut of bounded size can separate only a limited number of vertices from each part of the decomposition. Our techniques generalize to the weighted setting, where we seek for a bisection of minimum weight among solutions that contain at most k edges.