Hardness of Computing Weisfeiler-Lehman labels

Question

The 1-dim Weisfeiler-Lehman algorithm (WL) is commonly known as canonical labeling or color refinement algorithm. It works as follows :

• The initial coloring $C_0$ is uniform, $C_0(v) = 1$ for all vertices $v \in V (G) \cup V (H)$.
• In the $(i + 1)$ st round, the color $C_{i+1}(v)$ is defined to be a pair consisting of the preceding color $C_{i−1}(v)$ and the multiset of colors $C_{i−1}(u)$ for all $u$ adjacent to $v$. For example, $C_1(v) = C_1(w)$ iff $v$ and $w$ have the same degree.
• To keep the color encoding short, after each round the colors are renamed.

Given two undirected graphs $G$ and $H$, if the multiset of colors (aka labels) of the vertices of $G$ is distinct from the multiset of colors of the vertices of $H$, the algorithm reports that the graphs are not isomorphic; otherwise, it declares them to be isomorphic.

It is well-known that the 1-dim WL works correctly for all trees and requires only $O({\log}n)$ rounds.

My question is :

What is the hardness of computing 1-dim WL labels of a tree ? Is a lower bound better than logspace known ?

Answer 1

The problem of deciding whether two graphs have equivalent labelings and hence also the problem of computing the canonical labeling are PTIME complete. See

M. Grohe, Equivalence in finite-variable logics is complete for polynomial time. Combinatorica 19:507-532, 1999. (Conference version in FOCS'96.)

Note that colour refinement equivalence corresponds to equivalence in the logic C^2.

-Martin