Skip to content
DraconiticResearch
Search Sources API
186,123 studies31 sourcesUpdated 41 min ago
PreprintCC BY 4.0arXiv

Optimal Cuts and Optimal Faces of Exact Max-Cut Semidefinite Relaxations

  • Avinash Bhardwaj
  • Chen Chen
  • Vishnu Narayanan
Open at sourcePDFDOICite

Abstract

An exact Max-Cut semidefinite relaxation can have optima outside the convex hull of optimal cut matrices. We study when this hull equals the optimal face and how to recognize equality. For rational weights, the unique optimal dual slack is recoverable in polynomial time, but its kernel may contain directions no optimal matrix uses. Under strict complementarity, recognition and recovery of all optimal cuts on equality instances take deterministic polynomial time. At dual rank one, this hypothesis is unnecessary. Recognition is polynomial-time Turing equivalent to exact rational semidefinite feasibility, even on simple unweighted graphs. Testing whether a supplied cut matrix is the unique optimum is many-one equivalent, even on connected simple graphs with a unique optimal cut. NP-completeness of recognition would imply NP equals coNP. Replication realizes doubly nonnegative matrices with positive diagonal and rational kernel as sign-spanned optimal dual slacks, preserving rank, complete positivity, and cp-rank.

Related

  1. Exact Convex Reformulations of Binary Quadratic Programs from Facially Reduced Semidefinite Relaxations
    Hao Hu, Mingming Xu
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  2. Box-Cone Representations of Bound-Factor RLT Constraints in Semidefinite Relaxations
    Katherine Charbonneau, Hao Hu, Renata Sotirov
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  3. Optimal Control of State Constrained Systems via Measure Relaxations and Polynomial Optimization
    Saroj Prasad Chhatoi, Aneel Tanwani, Didier Henrion
    HALPreprintPublisher termsFull textOptimisation & controlHAL
  4. Optimal solution ranks in the Max-Cut semidefinite relaxation
    Avinash Bhardwaj, Vishnu Narayanan
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsOptimisation & controlarXiv
  5. Tractable Relaxations of Multivariate Stochastic Dominance via Optimal Transport and CVaR
    Bar Light
    arXivPreprintarXiv licenceFull textProbabilityarXiv

Cite

BibTeXRIS
BibTeX
@misc{bhardwaj2026optimal,
  title = {{Optimal Cuts and Optimal Faces of Exact Max-Cut Semidefinite Relaxations}},
  author = {Avinash Bhardwaj and Chen Chen and Vishnu Narayanan},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.36827},
  eprint = {2609.36827},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.36827},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Optimal Cuts and Optimal Faces of Exact Max-Cut Semidefinite Relaxations
AU  - Avinash Bhardwaj
AU  - Chen Chen
AU  - Vishnu Narayanan
PY  - 2026
DA  - 2026/10/11
PB  - arXiv
DO  - 10.48550/arxiv.2609.36827
UR  - https://arxiv.org/abs/2609.36827
AB  - An exact Max-Cut semidefinite relaxation can have optima outside the convex hull of optimal cut matrices. We study when this hull equals the optimal face and how to recognize equality. For rational weights, the unique optimal dual slack is recoverable in polynomial time, but its kernel may contain directions no optimal matrix uses. Under strict complementarity, recognition and recovery of all optimal cuts on equality instances take deterministic polynomial time. At dual rank one, this hypothesis is unnecessary. Recognition is polynomial-time Turing equivalent to exact rational semidefinite feasibility, even on simple unweighted graphs. Testing whether a supplied cut matrix is the unique optimum is many-one equivalent, even on connected simple graphs with a unique optimal cut. NP-completeness of recognition would imply NP equals coNP. Replication realizes doubly nonnegative matrices with positive diagonal and rational kernel as sign-spanned optimal dual slacks, preserving rank, complete positivity, and cp-rank.
ER  -