REPCAN-v2: A Polynomial-Time Candidate for Graph Isomorphism

§At a Glance

The Graph Isomorphism (GI) problem occupies one of the most remarkable positions in computational complexity: it is known to be in NP but has resisted decades of effort to prove either NP-complete or in P. László Babai's 2015 quasipolynomial-time algorithm — running in exp(polylog n) — placed GI tantalizingly close to P, but the polynomial-time gap remains the central open question in the area.

PRIMA was given the explicit charge to propose a solution, not survey the field. The 6-step program required the agents to (1) select the most promising attack vector, (2) develop concrete pseudocode, (3) submit the proposal to adversarial analysis against known hard instances (Cai–Fürer–Immerman graphs, strongly regular graphs, Paley graphs), (4) refine based on failures, (5) prove correctness and complexity, (6) assemble the result into a submission-grade research paper.

§The Challenge

The Graph Isomorphism problem asks whether two graphs G and H are structurally identical under vertex relabeling. Simple invariants — vertex count, edge count, degree sequence — are necessary but hopelessly insufficient. The challenge is finding a "fingerprint" (canonical form) that uniquely identifies each graph's structure efficiently.

A prior PRIMA survey run produced comprehensive coverage of the complexity landscape, algorithmic history, Babai's techniques, group-theoretic foundations, and 13 concrete open questions. That survey identified four structural prerequisites for a polynomial-time algorithm:

1. A complete graph invariant computable in polynomial time
2. An improved Split-or-Johnson dichotomy compressing recursion depth
3. Deeper exploitation of CFSG (Classification of Finite Simple Groups) internal structure
4. A non-group-theoretic complete invariant

This second program's mission: do not survey — propose a solution.

§Research Approach

The program was authored as a Phased PRIMA protocol with one cluster per step, prime-power agent identities, and strict dependency ordering. Each step's accept criteria were tuned to prevent the system from drifting into a survey:

• Original work required. Each step's criteria explicitly demanded results, pseudocode, or proof sketches — not literature summaries.
• Adversarial testing built in. Step 3 (testing) was explicitly tasked with trying to break the proposed algorithm against CFI, Paley, and strongly-regular hard families.
• Honest failure analysis demanded. A well-characterized failure (algorithm works for bounded-treewidth, fails on CFI) was treated as a genuine contribution.
• Conjectures permitted as conclusions. "Polynomial time conditional on Conjecture X" was an acceptable outcome — claiming unconditional polynomial time without rigorous proof was explicitly forbidden.

6-Step Execution DAG

Convergence Settings

§Key Findings

The agents converged on Johnson Fourier Refinement (JFR) as the most promising attack vector: a subroutine that projects external vertices' neighborhoods onto isotypic components of the Johnson scheme's Bose–Mesner algebra, extracting S_m-equivariant invariants in O(n³ log n) time — replacing the m! = exp(Θ(log n · log log n)) branching cost in Babai's Johnson base case.

The resulting algorithm, REPCAN-v2, is then augmented by Generalized Association Scheme Fourier Refinement (GASFR) for non-Johnson coherent configurations and retains Babai's fallback path for provably intractable instances.

3 Main Theorems Proved

5 Novel Conjectures Formally Stated

§The Johnson Bottleneck — What the Algorithm Bypasses

Babai's 2015 quasipolynomial algorithm proceeds through a Split-or-Johnson (SOJ) dichotomy applied to large color classes in the Weisfeiler–Leman stable coloring. For each large class X:

• Split case. A combinatorial certificate partitions X with bounded branching factor. Recursion depth and branching are tightly controlled — this case is polynomial-time per level.
• Johnson case. The class X has the combinatorial structure of the Johnson graph J(m, ℓ) — its vertices are ℓ-element subsets of an m-element ground set, with m = O(log n). The automorphism group Aut(J(m,ℓ)) ≅ S_m has order m! = exp(Θ(log n · log log n)), and Babai's standard resolution requires branching over the m! automorphisms to pin down a canonical labeling.

§The Mathematical Innovation — Fourier Analysis on the Johnson Scheme

The symmetric group S_m acts on the vertex set X = ([m] choose ℓ) of a Johnson scheme, making ℝ^X an S_m-module. By the theory of polynomial association schemes (Delsarte, 1973), this module decomposes into k+1 irreducible components:

DECOMPOSITIONℝ^X  =  V₀ ⊕ V₁ ⊕ V₂ ⊕ ... ⊕ V_k        where k = min(ℓ, m-ℓ)

Each V_i ≅ Specht module S^(m-i, i)

The key observation that drives REPCAN-v2:

This is the Johnson Fourier Refinement (JFR) subroutine, augmented by Generalized Association Scheme Fourier Refinement (GASFR) for non-Johnson coherent configurations. JFR replaces m!-cost branching with O(n³ log n)-cost Fourier projection.

The Orthogonal Projector Formula

Concretely, the i-th projector is computed from the Eberlein polynomials:

EQUATION           dim(V_i)    k
P_i  =  ─────────  ·  Σ  E_j^(m,ℓ)(i) · A_j
           |X|       j=0

dim(V_i)  =  C(m, i) − C(m, i−1)

where E_j^(m,ℓ)(i) is the Eberlein polynomial:

E_j^(m,ℓ)(i) =     j
                  Σ  (−1)^t · C(i,t) · C(m−i, j−t) · C(m−ℓ−j+t, ℓ−j)  /  C(m−i, j)
                  t=0

And the Equivariance Lemma guarantees these projectors commute with every permutation matrix π_σ for σ ∈ S_m: π_σ · P_i = P_i · π_σ. This is the mathematical fact that makes the projections isomorphism invariants.

§The REPCAN-v2 Algorithm in Detail

REPCAN-v2 computes a canonical adjacency matrix can(G) such that can(G) = can(H) ⟺ G ≅ H. The algorithm alternates between three phases:

1. WL-STABILIZE: refine the coloring using 1-dimensional Weisfeiler–Leman.
2. JFR-GASFR-PASS: apply Johnson Fourier Refinement (for Johnson-type classes) or Generalized Association Scheme Fourier Refinement (for general coherent configurations).
3. Fallback: when Phases 1–2 fail to progress, invoke Babai's branching subroutines (YOUNG-ENUM-RESOLVE for Johnson classes, BABAI-SPLIT for general).

Main Algorithm

PSEUDOCODE — REPCAN-v2Require:  Graph G = (V, E),  |V| = n
Ensure:   Canonical adjacency matrix can(G) ∈ {0,1}^(n×n)

 1:  C  ←  WL-STABILIZE(G, uniform coloring)
 2:  while some color class in C has size > 1 do
 3:      (changed, C)  ←  JFR-GASFR-PASS(G, C)
 4:      if changed then
 5:          C  ←  WL-STABILIZE(G, C)
 6:          continue
 7:      end if
 8:      X  ←  SELECT-LARGEST-CLASS(G, C)
 9:      (is_J, m, ℓ)  ←  IS-JOHNSON-TYPE(G, C, X)
10:      if is_J then
11:          C  ←  YOUNG-ENUM-RESOLVE(G, C, X, m, ℓ)     ← Babai fallback
12:      else
13:          C  ←  BABAI-SPLIT(G, C, X)                  ← Babai fallback
14:      end if
15:      C  ←  WL-STABILIZE(G, C)
16:  end while
17:  return  CONSTRUCT-CANONICAL-FORM(G, C)

Five Subroutines

§Complexity Analysis in Detail

The proof composes four cost lemmas:

Cost Lemma 1 — WL-STABILIZE

Cost Lemma 2 — Projector Computation

Cost Lemma 3 — The Core JFR-GASFR-PASS

Cost Lemma 4 — Outer Loop

Putting It Together

(a) Under PSS: at most n iterations × O(n³ log n) JFR-GASFR cost + WL-STABILIZE cost = O(n⁴ log n).

(b) Unconditionally: JFR-GASFR contributes O(n⁴ log n). Each fallback costs at most exp(O((log n)^c)). Over at most n fallback calls: n · exp(O((log n)^c)) = exp(O((log n)^c)) — matching Babai.

§Hard Instance Analysis — Four Adversarial Families

The adversarial step 3 of the program required the agents to attempt to break the proposed algorithm against four canonical hard families. The result is a detailed map of where REPCAN-v2 succeeds, where it partially succeeds, and where it is provably defeated.

CFI Graphs — A Provable Barrier (Negative Result)

The Cai–Fürer–Immerman (CFI) construction produces, for any 3-regular base graph H, a pair (G₀(H), G₁(H)) of non-isomorphic graphs that are indistinguishable by k-WL for any fixed k. They consist of vertex gadgets connected by edge connector pairs; the two graphs differ by a single gadget twist.

For CFI(K₄) with n = 28 vertices: WL produces two large color classes X₁ (16 gadget vertices) and X₂ (12 connector vertices), then stabilizes. Both copies of the CFI pair produce identical WL colorings. IS-JOHNSON-TYPE returns false for all classes. JFR-GASFR makes zero progress.

Proof sketch. For degree-3 gadgets, the coherent configuration CC(X) is a partition scheme isomorphic to the (ℤ/2)²-scheme, with Bose–Mesner idempotents π_χ = (1/4) · Σg χ(g) · Ag for characters χ ∈ Ĝ. The CFI twist T on a gadget is translation by some nonzero t ∈ (ℤ/2)², which is a group scheme automorphism: T·π_χ·T⁻¹ = π_χ. Therefore for any external vertex w:

PROOF KERNELK_twisted[i][w_a][w_b]  =  (F[w_a] · T⁻¹) · π_i · (T⁻¹)ᵀ · F[w_b]ᵀ
                       =  F[w_a] · T⁻¹·π_i·T · F[w_b]ᵀ
                       =  F[w_a] · π_i · F[w_b]ᵀ
                       =  K_original[i][w_a][w_b]

All Gram kernel values are identical in G₀ and G₁. Since 𝒜's only information comes from these kernels, it cannot distinguish the pair. QED.

The corollary: no polynomial-time algorithm whose power is equivalent to k-WL for any fixed k can distinguish all CFI pairs. The only way to resolve CFI instances is via the Babai-split fallback, which handles them in quasipolynomial time.

Strongly Regular Graphs — Partial Success

Paley Graphs — An Unexpected Positive Surprise

Nested Johnson Classes — Partial Resolution

Consider graphs with a large Johnson class X ≅ J(m, ℓ) and complex external structure. JFR applies correctly, but when two external vertices w_a, w_b satisfy F[w_a] ∈ Orb_Sm(F[w_b]), JFR leaves them with equal Gram kernels. The residual is resolved by recursive application of REPCAN-v2 on G[W], or by YOUNG-ENUM-RESOLVE if the symmetric structure persists.

JFR is complete for class X if and only if no two vertices u, v ∈ W with F[u] ∈ Orb_Sm(F[v]) need to be distinguished — which holds when G[W] is rigid.

§Comparison with Babai's Algorithm

§Fundamental Limitations

The paper is forthright about exactly where the approach fails. Three distinct boundaries:

1. The CFI Wall

2. The W = ∅ Problem (Vertex-Transitive Graphs)

3. The Recursion Depth Issue

§Two Open Problems Formalized

§Output Artifacts

The 6-step run produced a complete submission-grade research package:

§Why This Matters

This case study demonstrates four claims that single-shot LLM use cannot:

1. Multi-agent systems can produce original mathematical work. The output is not a literature survey or a restatement of known results — it is a new candidate algorithm, novel conjectures, and a previously-unrecorded impossibility result.
2. Adversarial step design protects against survey drift. By explicitly tasking step 3 with breaking the algorithm against CFI/Paley/SRG hard families, the orchestration prevents the agents from declaring premature success.
3. Honest failure analysis is contributive, not a defect. The CFI impossibility theorem only emerged because the design admitted "this approach fails on X" as a valid conclusion. A pipeline that rewards only positive results would have produced an overclaim.
4. Convergence threshold matters. Lowering global_threshold from 0.85 to 0.82 (paired with raising max_iterations from 8 to 10) was the difference between agents settling for surveys and agents committing to refined proposals.

Honest Limitations