Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements

Martin Grohe, Moritz Lichter, Daniel Neuen +1

The $k$-dimensional Weisfeiler-Leman ($k$-WL) algorithm is a simple combinatorial algorithm that was originally designed as a graph isomorphism heuristic. It naturally finds applic…