2025/12/04 by Joshua Brakensiek, Brakensiek, Joshua, Neng Huang +5
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2512.04951
openalex publication_date 2025/12/04 · openalex created_date 2025/12/06 · openalex updated_date 2026/07/28
The MAX BISECTION problem seeks a maximum-size cut that evenly divides the vertices of a given undirected graph. An open problem raised by Austrin, Benabbas, and Georgiou is whether MAX BISECTION can be approximated as well as MAX CUT, i.e., to within αGW≈ 0.8785672…, which is the approximation ratio achieved by the celebrated Goemans-Williamson algorithm for MAX CUT, which is best possible assuming the Unique Games Conjecture (UGC). They conjectured that the answer is yes. The current paradigm for obtaining approximation algorithms for MAX BISECTION, due to Raghavendra and Tan and Austrin, Benabbas, and Georgiou, follows a two-phase approach. First, a large number of rounds of the Sum-of-Squares (SoS) hierarchy is used to find a solution to the ``Basic SDP'' relaxation of MAX CUT which is ε-uncorrelated, for an arbitrarily small ε > 0. Second, standard SDP rounding techniques (such as \cal THRESH) are used to round this ε-uncorrelated solution, producing with high probability a cut that is almost balanced, i.e., a cut that has at most \frac12+ε fraction of the vertices on each side. This cut is then converted into an exact bisection of the graph with only a small loss. In this paper, we show that this two-stage paradigm cannot be used to obtain an αGW-approximation algorithm for MAX BISECTION if one relies only on the ε-uncorrelatedness property of the solution produced by the first phase. More precisely, for any ε > 0, we construct an explicit instance of MAX BISECTION for which the ratio between the value of the optimal integral solution and the value of some ε-uncorrelated solution of the Basic SDP relaxation is less than 0.87853 < αGW. Our instances are also integrality gaps for the Basic SDP relaxation of MAX BISECTION.