Improved inapproximability of Max-Cut through Min-Cut

Abstract: A cut is a partition of a graph's nodes into two sets, and we say that an edge crosses the cut if it connects two nodes belonging to different sets. A maximum cut is a cut that maximises the number of crossing edges. We show that for any sufficiently small ε > 0 it is NP-hard to distinguish between graphs for which at least a fraction 1 - ε of all edges crosses the maximum cut and graphs for which at most a fraction 1 - 1.4568 ε of all edges crosses the maximum cut. The previous state of the art had a constant smaller than 1.375 in place of 1.4568.