2026-07-23T04:33:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24393 2025-12-12T15:01:25Z ddc:004 open_access

Triangles Improve 0.878 Approximation for Maxcut George, Fredie Louis, Anand Paul, Rameesh Approximation Algorithms Maxcut Semidefinite Programming Edge-disjoint Triangles Unit Ball Graphs Spectral Triadic Graphs Maxcut is a fundamental problem in graph algorithms, extensively studied for its theoretical and practical significance. The goal is to partition the vertex set of a graph G = (V, E) into disjoint subsets S and V⧵S so as to maximize the number of edges crossing the cut (S,V⧵S). The seminal work of Goemans and Williamson [Goemans and Williamson, 1995] introduced a semidefinite programming (SDP) based algorithm achieving a α_{GW} ≈ 0.87856-approximation for general graphs, guaranteed to be optimal under the Unique Games Conjecture [Khot, 2002; Khot et al., 2007]. We revisit the Goemans–Williamson SDP and prove that the standard Maxcut SDP achieves a (α_{GW} + Ω(1))-approximation whenever the input graph contains Ω(|E|) edge-disjoint triangles. Our analysis builds on classical rounding techniques studied in [Goemans and Williamson, 1995; Zwick, 1999] and introduces a refined understanding of the SDP solution structure in regimes where the previous guarantees are tight. Our result identifies a simple combinatorial property that may be satisfied by many natural graph classes. As applications, we show that unit ball graphs and graphs satisfying a spectral transitivity condition (as studied in [Gupta et al., 2016; Basu et al., 2024]) meet our structural criterion, and therefore we get better than α_{GW} approximation guarantees for them. Our algorithm runs in nearly linear time 𝒪̃(|E|), offering a more practical alternative to the PTAS of [Jansen et al., 2005] for unit ball graphs, which has exponential dependence on the approximation parameter. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fredie George and Anand Louis and Rameesh Paul 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.27 urn:nbn:de:0030-drops-243931 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.27 eng https://creativecommons.org/licenses/by/4.0/legalcode