Computational complexity of the Weisfeiler-Leman dimension

DOI10.4230/LIPICS.CSL.2025.13MaRDI QIDQ7261419zbMATH OpenFDO

Authors Simon Raßmann, P. Schweitzer

Publication date 9 June 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.CSL.2025.13

zbMATH Keywords

coherent configurationscomplexitydimensionWeisfeiler-Leman algorithm

Mathematics Subject Classification ID

Logic in computer science (03B70)

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A partial k-arboretum of graphs with bounded treewidth
• An algorithmic meta theorem for homomorphism indistinguishability
• An exponential lower bound for individualization-refinement algorithms for graph isomorphism
• An optimal lower bound on the number of variables for graph identification
• Association schemes of small order
• Benchmark Graphs for Practical Graph Isomorphism
• Canonisation and Definability for Graphs of Bounded Rank Width
• Choiceless polynomial time on structures with small abelian colour classes
• Compressing CFI graphs and lower bounds for the Weisfeiler-Leman refinements
• Conflict propagation and component recursion for canonical labeling
• Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
• Distinguishing Vertices of Random Graphs
• Engineering an efficient canonical labeling tool for large and sparse graphs
• Equivalence in finite-variable logics is complete for polynomial time
• Fixed-point definability and polynomial time on graphs with excluded minors
• Graph isomorphism in quasipolynomial time (extended abstract)
• Graph isomorphism, color refinement, and compactness
• Graphs Identified by Logics with Counting
• scientific article; zbMATH DE number 3722702 (Why is no real title available?)
• scientific article; zbMATH DE number 3555903 (Why is no real title available?)
• Identifiability of graphs with small color classes by the Weisfeiler-Leman algorithm
• Logical hierarchies in PTIME
• On recognizing graphs by numbers of homomorphisms
• Parallel Computation of Combinatorial Symmetries.
• PEBBLE GAMES AND LINEAR EQUATIONS
• Practical graph isomorphism. II.
• Rank logic is dead, long live rank logic!
• Separating rank logic from polynomial time
• Sherali-Adams relaxations and indistinguishability in counting logics
• The Power of Counting Logics on Restricted Classes of Finite Structures
• The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3
• Treewidth is NP-complete on cubic graphs
• Witnessed symmetric choice and interpretations in fixed-point logic with counting

This page was built for publication: Computational complexity of the Weisfeiler-Leman dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7261419)