2026-08-17T06:29:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24386 2025-12-12T15:01:20Z ddc:004 open_access

Approximating Maximum Cut on Interval Graphs and Split Graphs Beyond Goemans-Williamson Ahn, Jungho DeHaan, Ian Kim, Eun Jung Lee, Euiwoong Maximum cut graph theory interval graphs split graphs We present a polynomial-time (α_{GW} + ε)-approximation algorithm for the Maximum Cut problem on interval graphs and split graphs, where α_{GW} ≈ 0.878 is the approximation guarantee of the Goemans-Williamson algorithm and ε > 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jungho Ahn and Ian DeHaan and Eun Jung Kim and Euiwoong Lee 2025 Is Part Of LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2025.20 urn:nbn:de:0030-drops-243869 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.20 eng https://creativecommons.org/licenses/by/4.0/legalcode