  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|| \leq 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^{O(k^{3})}n^3
\log^3 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.
