Skip to content
DraconiticResearch
Search Sources API
190,860 studies31 sourcesUpdated 38 min ago
PreprintCC BY 4.0arXiv

The Complexity of Recognizing SDP Exactness for the Maximum Cut Problem

  • Avinash Bhardwaj
Open at sourcePDFDOICite

Abstract

The standard semidefinite programming (SDP) relaxation of Max-Cut is exact when its optimum equals the maximum cut value. Delorme and Poljak resolved NP-completeness of recognizing exactness for weighted graphs and left the unweighted case open. We show that recognition is NP-complete even for connected simple unweighted graphs, and hence strongly NP-complete for nonnegative integer edge weights. The reduction provides an explicit SDP optimum and makes the additive integrality gap equal to the minimum number of unsatisfied clauses in the source formula. Recognition remains NP-complete even when an exact rational optimal primal--dual pair is supplied. We also establish strong NP-hardness of recognizing exactness of the Frieze--Jerrum Max-k-Cut relaxation for every fixed k≥3, even for connected graphs with nonnegative integer edge weights. An independent bounded-weight construction gives a second proof for Max-Cut. Finally, reductions preserving the additive gap up to explicit factors establish strong NP-completeness of exactness recognition for a basic Max-DiCut SDP and NP-hardness for a Max-Bisection SDP.

Related

  1. On the maximum relational complexity of affine groups
    Coen del Valle, Nick Gill, Pablo Spiga
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  2. The Maximum Principle and Optimal Gradient Estimates of Solutions to the Insulated Conductivity Problem
    Saibo Chen
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv
  3. Exact cost of the Euclidean Maximum Traveling Salesman Problem in one dimension
    Sergio Caracciolo, Carlo Vanoni
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsMathematical physicsarXiv
  4. Breaking the Odd Cycle: Regularization and First-Order Optimization for the Maximum s-Plex Problem
    Eleonora Bellesso, Immanuel M. Bomze, Francesco Rinaldi
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  5. Unbalanced spectral Turán problem for color-critical graphs with prescribed large maximum degree
    Chang Liu
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{bhardwaj2026complexity,
  title = {{The Complexity of Recognizing SDP Exactness for the Maximum Cut Problem}},
  author = {Avinash Bhardwaj},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.03508},
  eprint = {2609.03508},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.03508},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - The Complexity of Recognizing SDP Exactness for the Maximum Cut Problem
AU  - Avinash Bhardwaj
PY  - 2026
DA  - 2026/09/15
PB  - arXiv
DO  - 10.48550/arxiv.2609.03508
UR  - https://arxiv.org/abs/2609.03508
AB  - The standard semidefinite programming (SDP) relaxation of Max-Cut is exact when its optimum equals the maximum cut value. Delorme and Poljak resolved NP-completeness of recognizing exactness for weighted graphs and left the unweighted case open. We show that recognition is NP-complete even for connected simple unweighted graphs, and hence strongly NP-complete for nonnegative integer edge weights. The reduction provides an explicit SDP optimum and makes the additive integrality gap equal to the minimum number of unsatisfied clauses in the source formula. Recognition remains NP-complete even when an exact rational optimal primal--dual pair is supplied. We also establish strong NP-hardness of recognizing exactness of the Frieze--Jerrum Max-k-Cut relaxation for every fixed k≥3, even for connected graphs with nonnegative integer edge weights. An independent bounded-weight construction gives a second proof for Max-Cut. Finally, reductions preserving the additive gap up to explicit factors establish strong NP-completeness of exactness recognition for a basic Max-DiCut SDP and NP-hardness for a Max-Bisection SDP.
ER  -