The Weisfeiler-Lehman Procedure
V. Arvind · Bulletin of the European Association for Theoretical Computer Science · 2016
Perhaps the oldest algorithmic technique used for the Graph Isomorphism prob-lem is the Weisfeiler-Lehman procedure. Invented in the late 1960’s, it has attracted research in several directions over the last five decades, and continues to be an actively researched topic. Algorithmists invariably use this procedure in combination with others tools for Graph Isomorphism. Logicians interested in descriptive complexity have found logical characterizations for it. There is a linear programming connection to the Weisfeiler-Lehman procedure, and the Sherali-Adams hierarchy for the natural LP relaxation of a 0-1 integer linear pro-gram for Graph Isomorphism turns out to be intimately connected to ”higher dimensional” versions of the procedure. This brief essay, meant as an invitation to the topic, will touch upon these as-pects of the Weisfeiler-Lehman procedure. However, it is by no means a complete survey.