MathDB

Complexity of recognizing SDP exactness for Max-Cut on simple unweighted graphs

Given a finite simple unweighted graph G=(V,E)G=(V,E), decide whether the standard Goemans–Williamson semidefinite relaxation of Max-Cut has the same optimal value as the integer Max-Cut problem; equivalently, decide whether max⁡x∈{±1}V14∑{i,j}∈E(1−xixj)=max⁡vi∈R∣V∣∥vi∥=1 (i∈V)14∑{i,j}∈E(1−⟨vi,vj⟩)\max_{x\in\{\pm1\}^{V}}\frac{1}{4}\sum_{\{i,j\}\in E}(1-x_i x_j)=\max_{\substack{v_i\in\mathbb{R}^{|V|}\\\|v_i\|=1\ (i\in V)}}\frac{1}{4}\sum_{\{i,j\}\in E}(1-\langle v_i,v_j\rangle).

Equivalent formulations 1Other wordings

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

  1. Rank-one optimal solution formulation

    The SDP relaxation is exact if and only if it has an optimal solution of rank one, equivalently an optimal Gram matrix of the form X=xxTX=xx^{\mathsf T} with x∈{±1}Vx\in\{\pm1\}^{V}.

    source: On the Complexity of Recognizing SDP Exactness for the Maximum Cut Problem

References

Primary source

arXiv

Additional references

combinatorial-optimizationcomputational-complexitysemidefinite-programming
Posted

Progress summary

Refreshed
Claimed solved

A September 2026 preprint claims that checking whether the standard Max-Cut relaxation is exact is hard even for ordinary unweighted graphs, resolving the previously open case.

The problem asks for the computational complexity of recognizing when the Goemans–Williamson semidefinite relaxation exactly solves Max-Cut on simple unweighted graphs. The unweighted case had remained open, although weighted instances were already known to be NP-complete.

Known results

  • Delorme and Poljak proved NP-completeness for weighted graphs.
  • A 2025 preprint gave polynomial-time recognition for several characterized unweighted graph classes, while leaving the general case open.

September 2026 claimed hardness result

A new preprint claims strong NP-hardness for simple unweighted graphs, using polynomially bounded weighted reductions and a geometric embedding of restricted 44-SAT. If correct, this settles the explicitly open unweighted question and strengthens the weighted hardness result; the claim is unrefereed and awaits independent checking.

Current status (as of September 2026): NP-completeness is known for weighted graphs, while strong NP-hardness for simple unweighted graphs is claimed by a new preprint but remains unverified.

Sources

Solutions 0

No solutions have been posted yet.