A $2^{|E|/4}$-time Algorithm for MAX-CUT

In this paper we present an exact algorithm solving MAX-CUT in time $\operatorname{poly}(|E|)\cdot 2^{|E|/4}$, where $|E|$ is the number of edges (there can be multiple edges between two vertices). This bound improves the previously known bound $\operatorname{poly}(|E|)\cdot 2^{|E|/3}$ of Gramm et al. (2000).