Article Source

• Combinatorial Properties of the Weisfeiler-Leman Algorithm

Combinatorial Properties of the Weisfeiler-Leman Algorithm

• Speaker: Sandra Kiefer, RWTH Aachen
• Location: Calvin Lab Auditorium
• Presentation slides

Abstract

The Weisfeiler-Leman algorithm is a combinatorial procedure that plays a central role both in theoretical and practical research treating the graph isomorphism problem. For every k there is a k-dimensional version of the algorithm, which repeatedly and isomorphism-invariantly refines a partition of the set of k-tuples of vertices of the input graph. This process stabilizes at some point and the final partition can often be used to distinguish non-isomorphic graphs. To gain a better understanding of its precise complexity, we have investigated various properties of the algorithm. For example, we have studied the number of iterations until stabilization and have established for some graph classes upper bounds on the dimension that is needed to decide isomorphism. In this talk, I present some of those recent results.