graph isomorphism
A graph isomorphism is an isomorphism between two graphs \(G\) and \(H\) meaning that there exists \(f\) a bijection between the vertexes of \(G\) and those of \(H\) such that \((u, v)\) is an edge in \(G\) if and only if \((f(u), f(v))\) is an edge in \(H\).
Weisfeiler-Lehman algorithm
This algorithm computes an approximation of the graph isomorphism, but it has good properties on simple graph. In fact, it is more a family of algorithms parameterized by an integer \(k > 0\), each algorithm is denoted by $k$-WL. For \(k=1\), the algorithm performs in quasi-quadratic time. Usually, we present the algorithm for k=1 as an iterative refinement of a colorization of the graph nodes, such that the nodes having the same "neighborhood shape" are colored using the same color. When k>1, the color refinement concerns the k-tuples of nodes and the complexity is O(nk+1 log(n)).
I think that the following properties are correct:
- 1-WL is able to find the isomorphisms between the trees,
- 3-WL is able to find the isomorphisms between the planar graph.
References
- talks by Martin Grohe at KR 2021
