PaperlayerView exact revision on arXiv

Source-linked AI summary

The Complexity of Recognizing SDP Exactness for the Maximum Cut Problem

Avinash Bhardwaj

arXiv:2609.03508v3math.OCcs.CC

TL;DR

Exactness recognition asks whether the SDP optimum equals the maximum cut value, equivalently whether an optimal rank-one solution exists. Reductions encode Boolean satisfiability in partitioning graphs, with auxiliary vectors yielding explicit SDP optima and clause contributions determining discrete cut values. Exactness recognition is NP-complete for connected simple unweighted Max-Cut graphs even with an exact rational optimal primal–dual pair supplied, and is strongly NP-hard for fixed-k Max-k-Cut for k ≥3.

  • Problem

    Exactness recognition asks whether the SDP optimum equals the maximum cut value, equivalently whether an optimal rank-one solution exists.

    Source: §1 · p. 2

  • Method

    Reductions encode Boolean satisfiability in partitioning graphs, with auxiliary vectors yielding explicit SDP optima and clause contributions determining discrete cut values.

    Source: §3.1 · p. 5, §3.4 · p. 7

  • Results

    Exactness recognition is NP-complete for connected simple unweighted Max-Cut graphs even with an exact rational optimal primal–dual pair supplied, and is strongly NP-hard for fixed-k Max-k-Cut for k ≥3.

    Source: §6 · pp. 18–19

  • Takeaways & Limitations

    The hardness persists without large numerical weights and extends to the considered Max-DiCut and Max-Bisection relaxations.

    Source: §6 · pp. 18–19

    The results do not automatically extend to stronger semidefinite relaxations, whose additional constraints may exclude the vector assignments used in the reductions.

    Source: §6 · p. 19

Abstract

from arXiv · show

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\ge3$, 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.

1. Introduction

The paper studies when the standard Max-Cut SDP relaxation is exact and resolves the open recognition question for simple unweighted graphs. Its reductions establish hardness across Max-Cut and related partitioning relaxations, with explicit optima and additive-gap relationships.

1. Introduction

  • The SDP relaxation lifts scalar variables to unit vectors and, with randomized hyperplane rounding, yields an approximation ratio of approximately 0.878.Source: §1 · p. 1

1.2. Contributions.

  • Exactness recognition is NP-complete for connected simple unweighted Max-Cut graphs and strongly NP-complete for nonnegative integer edge weights.Source: §1.2 · p. 2
  • For each fixed assignment to variable vertices, optimizing auxiliary vertices yields cut contribution 9 for a satisfied clause and 8 otherwise; the relaxation is exact iff Φ is satisfiable.The source is linear monotone NAE-4-SAT: each clause has four distinct unnegated variables and is satisfied when their values are not all equal; any two clauses share at most one variable.Source: §1.2 · pp. 2–3
  • The additive integrality gap equals the minimum number of unsatisfied clauses, and connectedness is obtained while preserving both optimum values.Source: §1.2 · p. 3
  • The reduction supplies an exact rational optimal primal–dual pair, yet recognizing whether a cut attains the optimum remains NP-complete.The pair has polynomial encoding length.Source: §1.2 · p. 3
  • For every fixed k ≥3, recognizing exactness of the Frieze–Jerrum Max-k-Cut SDP is strongly NP-hard on connected graphs with nonnegative integer edge weights.Source: §1.2 · p. 3
  • A second Max-Cut construction proves strong NP-completeness for nonnegative integer weights without Kun’s theorem and allows clause contributions to accumulate as edge weights.Source: §1.2 · p. 3
  • The basic Max-DiCut SDP has strongly NP-complete exactness recognition, while the Max-Bisection SDP has NP-hard recognition on connected simple unweighted graphs.Both reductions preserve the Max-Cut additive integrality gap up to an explicit factor.Source: §1.2 · p. 3

2. Optimality Certificates

The section gives a polynomially checkable certificate for rank-one optimality and relates it to a signed-Laplacian condition on a cut. This yields NP membership for rational-weight Max-Cut exactness.

2. Optimality Certificates

  • For a candidate cut vector z, the rank-one matrix zz⊤ is optimal exactly when Diag(y) − B ⪰ 0 for y_i = z_i(Bz)_i.This choice of y follows from complementary slackness, and its rational encoding has polynomial length.Source: §2 · p. 4
  • For rational edge weights, a cut vector certifies Max-Cut SDP exactness by producing a slack matrix whose positive semidefiniteness can be checked in polynomial bit complexity.The resulting certificate has polynomial encoding length.Source: §2 · p. 4
  • Each certificate coordinate y_i is twice the weight of cut edges incident to vertex i, so no arbitrary real dual solution is needed.Source: §2 · p. 4

2.1. Signed-Laplacian interpretation.

  • A graph is exact exactly when some cut has a positive semidefinite cut-signed Laplacian, formed by retaining crossing-edge weights and reversing uncut-edge signs.Equivalently, the crossing-edge Laplacian dominates the uncut-edge Laplacian.Source: §2.1 · p. 4
  • This signed-Laplacian criterion is instance-dependent and does not require the whole graph to be bipartite.It expresses domination by the crossing-edge contribution for every real vector.Source: §2.1 · pp. 4–5

3. NP-Completeness for Connected Simple Unweighted Graphs

A reduction from linear monotone NAE-4-SAT makes Max-Cut SDP exactness equivalent to source-formula satisfiability. The construction establishes hardness for connected simple unweighted graphs, identifies the additive gap exactly, and retains hardness when an optimal primal–dual pair is supplied.

3.1. The Base Combinatorial Problem.

  • Linear monotone NAE-4-SAT is NP-complete, with each clause containing four distinct variables and any two clauses sharing at most one variable.Source: §3.1 · p. 5

3.2. The K6 Construction.

  • Each clause becomes a K6 with two private auxiliary vertices; linearity makes the cliques edge-disjoint in a simple unweighted graph.Source: §3.2 · p. 6

3.3. Continuous Bounds via Geometric Embedding.

  • The SDP optimum is 9m: orthogonal variable vectors and two auxiliary vectors cancel each clause’s variable-vector sum.Source: §3.3 · pp. 6–7

3.4. Combinatorial Exactness.

  • The additive gap equals the minimum number of unsatisfied clauses, so the SDP is exact precisely when the source formula is satisfiable.Source: §3.4 · p. 7
  • Identifying one auxiliary vertex from each component makes the graph connected while preserving both the cut and SDP optima.Source: §3.4 · p. 7
  • Exactness recognition is NP-complete for connected simple unweighted graphs and strongly NP-complete for nonnegative integer weights.Source: §3.4 · p. 8

3.5. Hardness with an optimal primal–dual pair supplied.

  • Recognition remains NP-complete when an exact rational optimal primal–dual pair of polynomial encoding length is included in the input.Source: §3.5 · p. 8

4. An Independent Bounded-Weight Construction

An independent reduction proves strong NP-hardness for weighted Max-Cut SDP exactness using polynomially bounded nonnegative integer weights. Its clause-wise square construction makes discrete attainment equivalent to satisfiability while the SDP bound is attained for every source formula.

4.2. The Matrix Construction and Its Gap.

  • Each clause contributes a squared penalty that auxiliary vectors cancel in the SDP; sign assignments make every penalty vanish exactly for satisfying formulas.Source: §4 · p. 9, §4.2 · p. 11

4.1. The Base Combinatorial Problem.

  • Monotone {3, 6}-in-9 SAT is NP-complete, with clauses satisfied when exactly three or six of nine distinct unnegated variables are true.Source: §4.1 · p. 9

4. An Independent Bounded-Weight Construction

  • The independent construction establishes strong NP-completeness for nonnegative integer weights of polynomial magnitude.Source: §4 · p. 9, §4.2 · p. 11

5. Extensions to Other Partitioning Problems

The section extends clause-based exactness reductions to Max-k-Cut, Max-DiCut, and Max-Bisection. It establishes hardness under the stated graph and weight restrictions, while noting that NP membership is not established for the Max-k-Cut and Max-Bisection formulations.

5. Extensions to Other Partitioning Problems

  • For Max-k-Cut and Max-Bisection, the results establish NP-hardness only, not NP membership.Additional constraints prevent direct application of the certificate lemma used for the basic Max-DiCut relaxation.Source: §5 · p. 12

5.1. Max-k-Cut.

  • At the SDP bound, k−2 shared anchors occupy distinct colors, leaving two colors whose balanced clause loads encode the Boolean constraints.A six-vertex clause block splits three-versus-three exactly when its four variables are not monochromatic, so a partition attains the bound if and only if the source formula is satisfiable.Source: §5.1 · pp. 12, 14
  • For fixed k, the construction has polynomial size and all weights are bounded by 9m, proving strong NP-hardness of deciding whether MCk(G)=SDPk(G).Source: §5.1 · p. 14

5.2. Max-DiCut.

  • For the basic Max-DiCut SDP, exactness recognition is strongly NP-complete on strongly connected digraphs with balanced weighted degrees and positive unequal opposite arc weights.The reduction preserves exactness from Max-Cut and uses polynomially bounded integer weights.Source: §5.2 · pp. 16–17

5.3. Max-Bisection.

  • Max-Bisection exactness recognition is NP-hard even on connected simple unweighted graphs, via two copies of a Max-Cut instance joined by a matching.The construction makes the bisection graph exact if and only if the original graph is exact.Source: §5.3 · pp. 17–18

6. Summary and Conclusion

The conclusion establishes hardness of recognizing exactness for Max-Cut and related partitioning SDPs, including when an exact rational optimal primal–dual pair is supplied. It also identifies the clause-level additive gap and notes a boundary: the reductions do not automatically extend to stronger semidefinite relaxations.

6. Summary and Conclusion

  • Max-Cut exactness recognition is NP-complete on connected simple unweighted graphs, and strongly NP-complete for nonnegative integer weights.The result resolves the unweighted recognition question left open by Delorme and Poljak.Source: §6 · p. 18
  • Supplying an exact rational optimal primal–dual pair still leaves exactness recognition NP-complete for the constructed instances.The SDP optimum and a rational optimal pair are available independently of satisfiability, but deciding whether a cut attains that optimum remains hard.Source: §6 · p. 18
  • The clause construction’s additive integrality gap equals the minimum number of unsatisfied clauses, but does not establish a constant relative gap.The source transformation preserves satisfiability, not a constant relative gap.Source: §6 · p. 18
  • Exactness recognition is also strongly NP-hard for fixed-k Max-k-Cut, strongly NP-complete for the basic Max-DiCut SDP, and NP-hard for Max-Bisection.The Max-k-Cut result holds for every fixed k ≥3 on connected graphs with nonnegative integer weights; the latter two reductions preserve the Max-Cut additive gap up to explicit factors.Source: §6 · p. 19
  • A proposed exact cut can be verified by a rational slack-matrix certificate, so recognition is polynomial-time on graph classes where a maximum cut is computable in polynomial time.The conclusion gives planar graphs and graphs of fixed bounded treewidth as examples.Source: §6 · p. 19
  • The reductions do not automatically establish hardness for stronger SDP relaxations, since their added constraints may exclude the vector assignments used to certify SDP values.Extending the approach requires a continuous certificate feasible for the stronger relaxation on both satisfiable and unsatisfiable instances.Source: §6 · p. 19
Loading 2609.03508v3…