[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.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	Target problem RSDF does not exist in the codebase; no existing path from MaximumClique to RSDF
Non-trivial	✅ Pass	Gadget construction using Motzkin-Straus theorem to encode clique structure into quartic sphere optimization
Correctness	✅ Pass	Both references verified: Gharibian (2009, arXiv:0810.4507) Theorem 2 confirms the reduction; Motzkin-Straus (1965) is a well-known classical result
Well-written	⚠️ Warn	Minor issues with overhead table and notation (see details below)

Overall: 3 passed, 0 failed, 1 warning

---

Usefulness

The target problem RobustSemidefiniteFeasibility (RSDF) does not exist in the reduction graph. pred show RSDF and pred show RobustSemidefiniteFeasibility both fail. This means a new model must be added before this rule can be implemented. Since no path from MaximumClique to any RSDF-like problem exists, this is a novel reduction. The motivation is clear: it establishes NP-hardness of RSDF via CLIQUE, which is relevant for quantum information (the Gharibian paper uses it to prove NP-hardness of the quantum separability problem).

Non-trivial

The reduction is genuinely non-trivial. It constructs k = n(n-1)/2 symmetric matrices (one per vertex pair), encodes the adjacency structure into their off-diagonal entries, and uses the Motzkin-Straus theorem to translate clique number into the maximum of a quartic form on the unit sphere. The promise gap construction (zeta, eta) involves careful algebraic manipulation. This is a bona fide structural transformation, not a relabeling or type coercion.

Correctness

Reference 1 — Gharibian (2009/2018), arXiv:0810.4507:
Verified. The paper defines RSDF in Definition 2 and proves the CLIQUE-to-RSDF reduction in Theorem 2, confirming:

• k = n(n-1)/2 matrices of dimension l = n
• Each B_i corresponds to a vertex pair with entries encoding adjacency
• The promise gap eta is in Omega(n^{-2})
• The reduction is polynomial-time

Reference 2 — Motzkin & Straus (1965), Canad. J. Math. 17, 533-540:
Verified. This is a classical result establishing that the maximum of a square-free quadratic form over the simplex equals (1/2)(1 - 1/omega(G)), where omega(G) is the clique number. The paper exists at the cited DOI (10.4153/CJM-1965-053-6).

Example verification:
The worked example (K_3, n=3, c=3) is mathematically consistent:

• Motzkin-Straus maximum = (1/2)(1 - 1/3) = 1/3
• g = 4 * 1/3 = 4/3
• Direct computation: each x^T B_i x = 2/3 at x = (1/sqrt(3), 1/sqrt(3), 1/sqrt(3)), so g = 3 * (2/3)^2 = 4/3
• YES threshold = 2(1 - 1/3) = 4/3, and g = 4/3 >= 4/3, so RSDF answers YES. Consistent.

Well-written

Strengths:

• All major template sections are present and substantive
• The reduction algorithm is detailed and step-by-step
• The example is fully worked with intermediate calculations
• Notation section is provided upfront

Warnings (not failures):

1. Overhead table uses asymptotic notation instead of exact formulas. The bit_size entry says "O(n^2)" and the promise gap says "Omega(n^{-2})". For the codebase's overhead system, exact polynomial expressions are needed (e.g., num_matrices = "num_vertices * (num_vertices - 1) / 2"). The bit_size and promise gap entries may not map to standard code metric names since RSDF is not yet implemented.

2. Target problem does not exist. RSDF must be implemented as a new model before this rule can be added. The issue should either reference an existing RSDF model issue or note that one needs to be created first.

3. Symbol A_G is introduced in the Notation section as "adjacency matrix" but only implicitly. The notation says "adjacency matrix A_G" which is acceptable, though making this a separate definition line would improve clarity.

4. The overhead table mixes code metric names with mathematical quantities. num_matrices and matrix_dim are plausible code field names, but bit_size of entries and promise gap eta are not standard code metric names. These should be reformulated once the RSDF model is defined.

Recommendations

• Create a companion [Model] issue for RobustSemidefiniteFeasibility before or alongside this rule issue, defining the struct fields and size getters
• Replace asymptotic overhead entries with exact formulas once the target model's size_fields are known
• Consider adding a NO-instance example (e.g., a path graph P_3 with c=3, where omega=2 < 3) to demonstrate both branches of the promise

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	Target problem RSDF does not exist in the codebase; no existing path from MaximumClique to RSDF
Non-trivial	✅ Pass	Non-trivial gadget construction using Motzkin-Straus encoding with quartic form over unit sphere
Correctness	✅ Pass	Both references verified; reduction matches Theorem 2 of Gharibian (2009)
Well-written	⚠️ Warn	Minor issues: overhead metrics reference a target problem not yet implemented; one notation concern

Overall: 3 passed, 0 failed, 1 warning

---

Usefulness

The target problem RobustSemidefiniteFeasibility (RSDF) does not currently exist in the reduction graph. There are no existing reductions from MaximumClique to RSDF (or any similar semidefinite feasibility problem). This reduction is novel and connects combinatorial graph problems to continuous optimization over semidefinite programs, which is valuable for quantum computing applications (the paper establishes NP-hardness of the quantum separability problem via this chain). Pass.

Non-trivial

The reduction involves genuine structural transformation:

• Constructs O(n^2) sparse symmetric matrices from the graph adjacency structure
• Uses the Motzkin-Straus theorem to encode clique number as a quartic optimization on the unit sphere
• Computes non-trivial promise gap thresholds (zeta, eta) from the clique size parameter
• The mapping between the simplex and unit sphere via y_i = x_i^2 is mathematically substantive

This is not a variable substitution, subtype coercion, or identity reduction. Pass.

Correctness

Reference 1: Gharibian (2009/2018), arxiv:0810.4507

• Paper exists: "Strong NP-Hardness of the Quantum Separability Problem" by Sevag Gharibian, published in Quantum Information & Computation, Vol. 10, No. 3&4, 2010.
• Theorem 2 confirmed: establishes a poly-time many-one reduction from CLIQUE instance (G, n, c) to RSDF instance (k, l, B_1,...,B_k, zeta, eta) with k = n(n-1)/2, l = n, eta in Omega(n^{-2}).
• The matrix construction described in the issue (sparse B matrices with entries at (s,t) and (t,s) set to A_G[s,t]) matches the paper.
• The promise gap structure and threshold derivation match the paper.

Reference 2: Motzkin & Straus (1965), doi:10.4153/CJM-1965-053-6

• Paper exists: "Maxima for Graphs and a New Proof of a Theorem of Turan" by T.S. Motzkin and E.G. Straus, Canadian Journal of Mathematics, Vol. 17, pp. 533-540, 1965.
• The theorem max_{x in simplex} sum_{(i,j) in G} x_i x_j = (1/2)(1 - 1/omega) is the classical Motzkin-Straus result and is correctly stated.

Both references are real, correctly cited, and support the claims made. Pass.

Well-written

4a: Information Completeness — All required sections are present and substantive: Source, Target, Motivation, Reference, Reduction Algorithm, Size Overhead, Validation Method, and Example.

4b: Algorithm Completeness — The reduction algorithm is a complete, step-by-step procedure. Matrix construction is explicit (step 1), threshold computation is fully derived (step 2), and correctness argument is provided. A programmer could implement this directly.

4c: Symbol and Notation Consistency — Mostly good. All symbols (n, c, A_G, omega, g, zeta, eta) are defined before use. Minor concern: the overhead table uses num_matrices and matrix_dim as code metric names, but since RSDF does not yet exist as a model, these getter names cannot be verified against actual size_fields. The bit_size metric uses big-O notation which is unusual for overhead tables that typically use exact polynomial expressions. Warn.

4d: Example Quality — The K_3 example is fully worked through with step-by-step verification:

• Source instance clearly stated (K_3, n=3, c=3, omega=3)
• All three B matrices explicitly written out
• Numerical verification: g = 4/3 matches 2(1 - 1/3) = 4/3
• Promise threshold check: g >= zeta + eta confirmed

The example is small enough to verify by hand but exercises all aspects of the reduction. However, a K_3 triangle is a relatively simple case — all vertices are in the clique. A slightly more interesting example might include non-edges to show that B matrices for non-edges are zero matrices. This is a minor suggestion, not a failure.

Recommendations

• Consider adding a second example with a graph that has non-edges (e.g., a path graph P_3 with c=2) to demonstrate how non-edge pairs produce zero matrices and affect the optimization value.
• The RSDF model will need to be implemented first before this reduction rule can be added. Consider filing a [Model] issue for RSDF.
• The bit_size overhead entry uses asymptotic notation (O(n^2)) rather than an exact expression. For the #[reduction(overhead = {...})] macro, exact polynomial expressions are required. Consider replacing with a concrete formula.
• The note in the issue says the paper is "Gharibian, S. (2009/2018)" — the paper was submitted in 2008, published in QIC in 2010 (Vol. 10, No. 3&4). The year attribution could be clarified.

[GiggleLiu]

Closing as part of batch cleanup.