Approximating Maximum Cut on Interval Graphs and Split Graphs beyond Goemans-Williamson

Abstract

We present a polynomial-time $(\hat{I}{\pm }_{GW}+\epsilon )$-approximation algorithm for the Maximum Cut problem on interval graphs and split graphs, where $\hat{I}{\pm }_{GW}\approx 0.878$ is the approximation guarantee of the Goemans-Williamson algorithm and $\epsilon >10^{-34}$ is a fixed constant. To attain this, we give an improved analysis of a slight modification of the Goemans-Williamson algorithm for graphs in which triangles can be packed into a constant fraction of their edges. We then pair this analysis with structural results showing that both interval graphs and split graphs either have such a triangle packing or have maximum cut close to their number of edges. We also show that, subject to the Small Set Expansion Hypothesis, there exists a constant $c>0$ such that there is no polyomial-time $(1-c)$-approximation for Maximum Cut on split graphs.

23 pages, 5 figures, to appear in the proceedings of APPROX 2025