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

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.