{"id":"openai-math/Variable-dimension-Weisfeiler-Leman-equivalence-on-general-and-subcubic-graphs","pdf":"https://github.com/openai/math/blob/main/preprints/Variable-dimension-Weisfeiler-Leman-equivalence-on-general-and-subcubic-graphs-September-25-2026/paper.pdf","url":"https://github.com/openai/math/tree/main/preprints/Variable-dimension-Weisfeiler-Leman-equivalence-on-general-and-subcubic-graphs-September-25-2026","tags":["graph-isomorphism","complexity-theory","weisfeiler-leman"],"score":0,"title":"Variable-dimension Weisfeiler–Leman equivalence on general and subcubic graphs","domain":"Theoretical computer science","family":"133","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"Deciding joint-update k -dimensional Weisfeiler–Leman equivalence is $`\\mathsf{EXPTIME}`$-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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-25","reactions":{},"formalized":false,"family_title":"The computational complexity of Weisfeiler–Leman refinement"}