On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets

Abstract

Max-Cut is a classical graph-partitioning problem where given a graph $G=(V,E)$, the objective is to find a cut $(S,S^c)$ which maximizes the number of edges crossing the cut. In a seminal work, Goemans and Williamson gave an ${\alpha }_{GW}\approx 0.87856$-factor approximation algorithm for the problem, which was later shown to be tight by the work of Khot, Kindler, Mossel, and O'Donnell. Since then, there has been a steady progress in understanding the approximability at even finer levels, and a fundamental goal in this context is to understand how the structure of the underlying graph affects the approximability of the Max-Cut problem. In this work, we investigate this question by exploring how the chromatic structure of a graph affects the Max-Cut problem. While it is well-known that Max-Cut can be solved perfectly and near-perfectly in $2$-colorable and almost $2$-colorable graphs in polynomial time, here we explore its approximability under much weaker structural conditions such as when the graph is $3$-colorable or contains a large independent set. Our main contributions in this context are as follows: 1. We show Max-Cut is ${\alpha }_{GW}$-hard to approximate for $3$-colorable graphs. 2. We identify a natural threshold ${\alpha }^{\ast }$ such that the following holds. Firstly, for graphs which contain an independent set of size up to ${\alpha }^{\ast }$, Max-Cut continues to be ${\alpha }_{GW}$-factor hard to approximate. Furthermore, for any graph that contains an independent set of size $>{\alpha }^{\ast }$, there exists an efficient $>{\alpha }_{GW}$-approximation algorithm for Max-Cut. Our hardness results are derived using various analytical tools and novel variants of the Majority-Is-Stablest theorem, which might be of independent interest. Our algorithmic results are based on a novel SDP relaxation, which is then rounded and analyzed using interval arithmetic.

56 Pages. Abstract is shortened to fit arXiv requirements