[Rule] MaximumClique to RSDF

[QingyunQian]

Source: MaximumClique
Target: RobustSemidefiniteFeasibility (RSDF)
Motivation: Establishes NP-hardness of RSDF via a many-one reduction from the NP-complete problem CLIQUE, using the Motzkin-Straus theorem to encode clique number as a quartic optimization on the unit sphere.
Reference:

• Gharibian, S. (2009/2018). Strong NP-Hardness of the Quantum Separability Problem. (Theorem 2, lines 229-252)
• Motzkin, T. S. & Straus, E. G. (1965). "Maxima for graphs and a new proof of a theorem of Turán." Canad. J. Math., 17, 533–540.

Reduction Algorithm

Notation:

• Source (CLIQUE): simple graph G on n vertices with adjacency matrix A_G, and clique-size threshold c; question: does G contain a complete subgraph of size >= c?
• Target (RSDF): k symmetric rational l × l matrices B_1, ..., B_k, and rationals zeta, eta >= 0, with

g(B_1,...,B_k) = max_{||x||_2=1} sum_{i=1}^k (x^T B_i x)^2.

Promise:

• YES if g >= zeta + eta
• NO if g <= zeta - eta

Direct Mapping (CLIQUE -> RSDF):

Set k = n(n - 1)/2 and l = n.

1. Matrix construction:
   For each pair 1 <= s < t <= n, construct one matrix B_{(s,t)} of size n × n:

   • All entries are zero except positions (s, t) and (t, s), which are set to A_G[s, t] (the adjacency entry).
   • If (s, t) is an edge, these entries are 1; otherwise 0.

   This gives k = n(n-1)/2 matrices, one per vertex pair.

2. Threshold construction:
   Using the Motzkin-Straus theorem, the maximum clique number omega(G) satisfies:

   max_{x in simplex} sum_{(i,j) in G} x_i x_j = (1/2)(1 - 1/omega).
   

   Since g = 4 * max_{simplex} sum y_i y_j (via substitution y_i = x_i^2), we have:

   g_max = 2(1 - 1/omega(G)).
   

   The RSDF thresholds are set as:

   g_YES >= 2(1 - 1/c)          (when omega >= c)
   g_NO  <= 2(1 - 1/(c - 1))    (when omega < c)
   
   zeta + eta = 2(1 - 1/c)
   zeta - eta = 2(1 - 1/(c - 1))
   eta = 1/(c(c - 1))           which is Omega(n^{-2}) since c <= n.
   

Correctness (Theorem 2 in Gharibian):

The quartic form g over the unit sphere encodes the same combinatorial optimization as the Motzkin-Straus quadratic form over the simplex. The B_i matrices extract cross terms x_s x_t for each edge, and squaring produces a quartic whose maximum reflects the clique number. The promise gap eta in Omega(n^{-2}) is polynomially bounded, ensuring the reduction is polynomial-time.

Size Overhead

Target metric (code name)	Polynomial (using symbols above)
num_matrices (k)	n(n - 1)/2
matrix_dim (l)	n
bit_size of entries	O(n^2) (each B_i has at most 2 nonzero entries, each 0 or 1)
promise gap eta	Omega(n^{-2})

Validation Method

• On small graphs (n <= 10), brute-force CLIQUE and compare with numerical evaluation of g on the constructed RSDF instance
• Verify B_i matrix structure: exactly one matrix per vertex pair, nonzero entries only at (s,t) and (t,s)
• Cross-check g value against Motzkin-Straus formula: g should equal exactly 4 * (1/2)(1 - 1/omega) = 2(1 - 1/omega) (since g = 4 * sum y_i y_j where y_i = x_i^2 maps the unit sphere to the simplex)
• Test on graphs with known clique numbers (e.g., Petersen graph: omega = 2, complete graph K_5: omega = 5)

Example

Source CLIQUE instance

G = triangle (K_3), n = 3, c = 3
Vertices: {1, 2, 3}
Edges: {(1,2), (1,3), (2,3)}
omega(G) = 3 >= c = 3 => CLIQUE YES

Target RSDF image

l = n = 3, k = n(n-1)/2 = 3

B_{(1,2)}: only (1,2) and (2,1) = 1 (edge exists)
B_{(1,2)} = [[0, 1, 0],
             [1, 0, 0],
             [0, 0, 0]]

B_{(1,3)}: only (1,3) and (3,1) = 1
B_{(1,3)} = [[0, 0, 1],
             [0, 0, 0],
             [1, 0, 0]]

B_{(2,3)}: only (2,3) and (3,2) = 1
B_{(2,3)} = [[0, 0, 0],
             [0, 0, 1],
             [0, 1, 0]]

Motzkin-Straus: max over simplex (sum y_i = 1) = (1/2)(1 - 1/3) = 1/3
Achieved at y = [1/3, 1/3, 1/3].

By substituting y_i = x_i^2, we map this to the unit sphere (sum x_i^2 = 1).
On unit sphere x = [1/sqrt(3), 1/sqrt(3), 1/sqrt(3)]:
  x^T B_{(1,2)} x = 2 * (1/sqrt(3)) * (1/sqrt(3)) = 2/3
  x^T B_{(1,3)} x = 2/3
  x^T B_{(2,3)} x = 2/3
  g = (2/3)^2 + (2/3)^2 + (2/3)^2 = 3 * 4/9 = 4/3

Check: g = 2(1 - 1/omega) = 2(1 - 1/3) = 4/3. Consistent.

For c = 3: YES threshold = 2(1 - 1/c) = 4/3.
Since g = 4/3 >= 4/3, RSDF answers YES.