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 ?


1 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.


  • 3
    $\begingroup$ Hi Martin. Welcome to cstheory. $\endgroup$
    – Kaveh
    Nov 19, 2012 at 0:50
  • $\begingroup$ @Martin What is the best known hardness of computing the WL-labels of minor-free graphs ? Is it still P-complete ? I am trying to prove that Graph Isomorphism of minor-free graphs is in AC1. $\endgroup$ Nov 19, 2012 at 22:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.