Weisfeiler–Leman Equivalence Remains EXPTIME-Complete on Subcubic Graphs

Two graphs can have the same number of vertices and the same degree at every vertex without being distinguishable by those facts alone. Weisfeiler–Leman refinement, or WL, gives a stronger fingerprint by labeling ordered tuples of vertices. Its dimension (k) is the number of positions in each tuple.

For any fixed (k), the refinement runs in polynomial time. The harder question is what happens when (k) is part of the input. The manuscript claims that deciding whether two graphs have matching fingerprints is EXPTIME-complete—even when the graphs are connected and every vertex has at most three neighbors. ^†

The target is specific: given an explicit pair of graphs and a supplied dimension, decide whether they are equivalent under joint (k)-dimensional refinement. This is not a question about graph isomorphism or finding the smallest dimension that distinguishes two graphs.

In dimension 2, an ordered pair begins with a label describing whether its vertices are equal, adjacent, or distinct non-neighbors. For each vertex (z), replace the first position by (z), then replace the second position by that same (z). Keep the two resulting labels together as one ordered vector. The new label records the multiset of these vectors, along with the pair’s old label.

“Joint” matters: splitting each vector into separate collections would lose the information about which replacements came from the same vertex. In dimension (k), each replacement contributes a vector of (k) labels.

A six-vertex example makes the distinction concrete. In a triangular prism, an edge within a triangle has a third vertex adjacent to both endpoints. Replacing each endpoint in turn with that vertex produces the vector ((A,A)), where (A) denotes adjacency. In the comparison graph—a complete bipartite graph with three vertices on each side—no vertex is adjacent to both ends of an edge, so that vector does not occur for an edge there.

The resulting edge-label counts differ, so the graphs are not equivalent at (k=2). This pair illustrates how the rule works; it is not the hardness construction. Equivalence requires the complete tuple-label counts to agree at every round, using the same label names.

The exponential-time upper bound does not require constructing a tuple table whose size follows an arbitrarily large input value of (k). If the graphs have the same order (n), with (n\ge 2), then (k) can be capped at (n).

Once (k\ge n), a tuple can contain every vertex. If two such tuples have the same initial label, they preserve all equalities and adjacencies among the vertices, and therefore describe an isomorphism. Conversely, an isomorphism preserves every subsequent WL label. Thus the effective dimension is (\min(k,n)).

The algorithm checks the input conditions, including whether the graph orders match, rather than expanding a binary-encoded (k) into an enormous table. With the effective dimension capped, the combined tables have at most (2n^n) entries. Each strict refinement splits a label class, so the number of rounds is bounded by the number of possible classes. The manuscript uses this to bound the computation by exponential time in the explicit input length. Unequal orders are rejected, while orders zero and one are handled separately.

For the lower bound, the manuscript gives an equivalent game characterization. For equal positive-order graphs and (k\ge2), play starts with (k+1) empty slots for matched vertex pairs. Spoiler can discard pairs and ask for an empty slot. Duplicator must then announce a bijection between the entire vertex sets; only after that does Spoiler choose a vertex. The announced bijection determines its partner.

Every marked pair must preserve equality and adjacency. The order of moves is essential: Duplicator must commit to the whole bijection before learning which vertex will be selected. The manuscript proves that one Duplicator strategy survives every finite play exactly when the graphs are equivalent under joint (k)-dimensional refinement.

The reduction uses this game to encode an exponential-time computation in a polynomial-size instance. Binary addresses describe time and tape position; carry rules describe neighboring addresses without listing the exponentially long computation. These rules give a polynomial-size description of an exponentially large circuit.

Its consistency mechanism relies on nonempty sets of one-bit or two-bit values. For each connection, individual scalar images must match, but the construction does not require one simultaneous vector assignment. This distinction lets separate comparisons use different members of the same set.

A two-bit buffer carries that distinction. Arithmetic is over the binary field, where (1+1=0). A “true” source is represented by the singleton ({0}); a false source can retain ({0,1}). If the source image is ({0}), both coordinates in every buffer pair must be zero, forcing the destination to ({0}). If the source image is ({0,1}), the pairs ((0,1)) and ((1,0)) make every sum one, while ((0,0)) and ((1,1)) make every sum zero. Using all four pairs allows both sums. A full source image can therefore support any nonempty destination image. These are separate image equalities, not one assignment required to satisfy all comparisons at once.

The buffer handles how consistency propagates through the encoded computation; another step is needed to make those local comparisons usable in the game. The manuscript compresses addressed comparisons into small affine blocks. Its exact-extension result says that compatible offsets already selected can be preserved while one more block is added within the game’s slot limit.

Before announcing a bijection, Duplicator prepares an extension for each inactive block. Those extensions need not agree: Spoiler’s next vertex activates at most one block. The aim is to have a compatible extension ready for whichever block becomes active, not one extension that works for every possible next move.

The proof connects these local choices to a global move by collecting sets of attainable sums across histories of one fixed winning strategy. A later visit may produce a different answer. The construction copies source sites into squares before discarding anything, so values can be compared at a common position; only then are the squares copied to destination sites. Transfers in both directions establish equality of the separate scalar images. The explainer presents this as a roadmap and omits the full extension and recognition proofs.

The construction reduces the degree of the output graphs using valuation paths, binary prefix trees, and matchings that test shared values, with an anchor path connecting the blocks. Temporary vertex sorts are encoded structurally: each vertex is replaced by a triangle, one connector is attached to each corner, and a private path records the sort. Each connector can take at most one external edge; the triangle vertices have degree three.

The resulting graphs are uncolored and need not be regular. The manuscript says its recognition argument preserves the encoded information in the game and that both explicit adjacency matrices can be produced in polynomial time, even as the dimension grows.

The claimed theorem establishes EXPTIME-completeness: an exponential-time upper bound and a polynomial-time reduction from every deterministic EXPTIME problem. Its restrictions include explicit, simple, connected, uncolored graphs of equal positive order, maximum degree at most three, and a supplied binary dimension (k\ge2).

The accompanying explainer reports that small checks verified displayed examples, not the entire theorem, and that formal reproduction was not run. It describes itself as an original explainer of the OpenAI manuscript, not an official OpenAI production.