Open Research Index

The Complexity of Recognizing SDP Exactness for the Maximum Cut Problem

Avinash Bhardwaj

arXivarxiv/2609.03508Sep 3, 2026math.OCscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2609.03508
curl -X POST /api/v1/records/arxiv/2609.03508/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.03508/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'