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

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

<p>Note that colour refinement equivalence corresponds to equivalence in the logic C^2.</p>

<p>-Martin</p>

CC BY-SA 3.0
2012-11-19T00:50:28.297Z
Hi Martin. Welcome to cstheory.
Kaveh
CC BY-SA 3.0
2012-11-19T22:51:20.730Z
@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.
Shiva Kintali
CC BY-SA 3.0
2012-11-18T12:06:53.487Z
2012-11-18T12:06:53.487Z
Martin Grohe
<p>The <strong>1-dim Weisfeiler-Lehman algorithm</strong> (WL) is commonly known as canonical labeling or color refinement algorithm. It works as follows :</p>

<ul>
<li>The initial coloring $C_0$ is uniform, $C_0(v) = 1$ for all vertices $v \in V (G) \cup V (H)$.</li>
<li>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.</li>
<li>To keep the color encoding short, after each round the colors are renamed.</li>
</ul>

<p>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.</p>

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

<p>My question is :</p>

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

<cc.complexity-theory><graph-theory><graph-isomorphism><logspace>
Hardness of Computing Weisfeiler-Lehman labels
Shiva Kintali
# Hardness of Computing Weisfeiler-Lehman labels

(Asked by: username_0 on 2012-03-03)

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 ?

**Tags:** cc.complexity-theory, graph-theory, graph-isomorphism, logspace


---

## 1 answers

### Answer by username_1 on 2012-11-18. Score: 11

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

> **Comments:**
> **username_2**: Hi Martin. Welcome to cstheory.  
> **username_0**: @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.  

---

