Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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 ?

share|improve this question

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.

-Martin

share|improve this answer
3  
Hi Martin. Welcome to cstheory. –  Kaveh Nov 19 '12 at 0:50
    
@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 Nov 19 '12 at 22:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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