Steklov Institute of Mathematics at St.Petersburg

PREPRINT 11/2002

A $2^{|E|/4}$-TIME ALGORITHM FOR MAX-CUT

This preprint was accepted June 10, 2002
Contact: S. Fedin and A. Kulikov

ABSTRACT:

In this paper we present an exact algorithm solving MAX-CUT in time $\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 $\poly(|E|)\cdot 2^{|E|/3}$ of \cite{GHNR00}.