{"ID":2894953,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.10436","arxiv_id":"2507.10436","title":"Approximating Maximum Cut on Interval Graphs and Split Graphs beyond Goemans-Williamson","abstract":"We present a polynomial-time $(α_{GW} + \\varepsilon)$-approximation algorithm for the Maximum Cut problem on interval graphs and split graphs, where $α_{GW} \\approx 0.878$ is the approximation guarantee of the Goemans-Williamson algorithm and $\\varepsilon \u003e 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 \u003e 0$ such that there is no polyomial-time $(1 - c)$-approximation for Maximum Cut on split graphs.","short_abstract":"We present a polynomial-time $(α_{GW} + \\varepsilon)$-approximation algorithm for the Maximum Cut problem on interval graphs and split graphs, where $α_{GW} \\approx 0.878$ is the approximation guarantee of the Goemans-Williamson algorithm and $\\varepsilon \u003e 10^{-34}$ is a fixed constant. To attain this, we give an impr...","url_abs":"https://arxiv.org/abs/2507.10436","url_pdf":"https://arxiv.org/pdf/2507.10436v1","authors":"[\"Jungho Ahn\",\"Ian DeHaan\",\"Eun Jung Kim\",\"Euiwoong Lee\"]","published":"2025-07-14T16:24:20Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}