{"id":"openai-math/The-complexity-of-identifying-a-graph-by-Weisfeiler-Leman-refinement","pdf":"https://github.com/openai/math/blob/main/preprints/The-complexity-of-identifying-a-graph-by-Weisfeiler-Leman-refinement-September-25-2026/paper.pdf","url":"https://github.com/openai/math/tree/main/preprints/The-complexity-of-identifying-a-graph-by-Weisfeiler-Leman-refinement-September-25-2026","tags":["graph-theory","computational-complexity","weisfeiler-leman"],"score":0,"title":"The complexity of identifying a graph by Weisfeiler–Leman refinement","domain":"Theoretical computer science","family":"133","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"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.","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"}