The Escaped Boundary

The Weisfeiler-Lehman hierarchy defines a complexity ladder for distinguishing non-isomorphic graphs. At level k, the algorithm refines k-tuples of vertices until stable. Higher levels distinguish more graphs but cost more time. The classical Rook L₂(4) versus Shrikhande pair — both SRG(16,6,2,2) — is indistinguishable at level 3.

DRESS separates them in polynomial time.

The method is combinatorially simple: apply single vertex deletion to a graph fingerprint, generating Δ-DRESS signatures. Across 34 benchmark families of strongly regular graphs — 51,718 non-isomorphic instances — Δ-DRESS achieves 100% within-family separation. The complexity is O(n · I · m · d_max) per graph, clearly polynomial.

The escape from 3-WL isn’t through more refined tuple coloring. It’s through a structural operation (deletion) that the WL framework doesn’t perform. The hierarchy measures refinement depth; DRESS operates orthogonally, using perturbation rather than iteration.

This doesn’t resolve graph isomorphism complexity — separation of known hard families is evidence, not proof. But it demonstrates that the WL hierarchy’s limitations are specific to its mechanism, not to the problem’s intrinsic difficulty. The boundary the algorithm crosses isn’t a wall. It’s a fence around a particular method.

What 3-WL cannot see, deletion reveals. The graph was always distinguishable — the question was which operation made the distinction visible.