Family 133Theoretical computer scienceNo LeanNot yet digested
The computational complexity of Weisfeiler–Leman refinement
Proves unconditional deterministic time lower bounds for joint and separate k-dimensional Weisfeiler–Leman equivalence, for sufficiently large fixed k in the specified sequential adjacency-matrix models. With dimension as input, joint equivalence is EXPTIME-complete even on subcubic graphs; deciding whether refinement identifies a graph is also EXPTIME-complete.
Manuscripts in this family · 4
Parity lifts and bounded-treewidth witnesses for Weisfeiler–Leman equivalence
Sep 25, 2026·paper.pdf
For k ≥ 4, we construct two uncolored graphs that are k-dimensional Weisfeiler–Leman equivalent exactly when a prescribed finite-domain choice system has no compatible choice. The system has domains for joint refinement and k for separate-coordinate refinement. A successful choice is detected after two joint rounds or one separate round. Applied to sparse satisfiability, the reduction gives fixed-dimension time exclusions under positive-rate ETH, even for deciding equality of these early histograms.
The complexity of identifying a graph by Weisfeiler–Leman refinement
Sep 25, 2026·paper.pdf
We prove that deciding whether Weisfeiler–Leman refinement of an input dimension identifies a given graph is EXPTIME-complete. The input is a nonempty finite simple uncolored graph in adjacency-matrix form and a positive binary-encoded dimension. Identification quantifies over every comparison graph.
Unconditional time lower bounds for Weisfeiler–Leman equivalence
Sep 25, 2026·paper.pdf
For every sufficiently large fixed k, deciding whether two n-vertex graphs are k-Weisfeiler–Leman equivalent requires deterministic sequential time in the worst case. The bound holds at every sufficiently large graph order, even for simple connected uncolored graphs of diameter at most two, without a complexity assumption. Inputs are explicit adjacency matrices; the models are multitape Turing machines and sequential logarithmic-word RAMs with fixed polynomial-bit-time instructions. Both joint and separate replacement conventions are covered.
Variable-dimension Weisfeiler–Leman equivalence on general and subcubic graphs
Sep 25, 2026·paper.pdf
Deciding joint-update k-dimensional Weisfeiler–Leman equivalence is -complete when the two graphs are given by explicit adjacency matrices and k ≥ 2 is encoded in binary. The result holds even for connected simple uncolored graphs of equal positive order and maximum degree at most three.