Graph Isomorphism is a very well known problem in computer science. A generic procedure for the graph isomorphism problem builds on a simple color refinement procedure given below (One dimensional Weisfeiler–Lehman Procedure)

  • To begin with, all vertices have the same color.
  • In each color refinement step, if two vertices $u$ and $v$ have the same color but their neighbourhood are differently coloured (counting color multiplicity), then $u$ and $v$ get fresh different colours.

Please note that for $k$-WL runs at most $|V|^k$ refinement steps. See this paper by V. Arvind

Question 1: What is the tight upper bound on the number of iterations of Weisfeiler–Lehman Procedure?

I know that if the given input graphs are regular then in a one step (one iteration) algorithm will stop. I am thinking like this there is going to be partitioning of the vertices and in each iteration a partition can only split, so in the worst case at the end I can have at most $n-2$ partitions.

Question 2 : Are there graph classes not able to distinguish by color refinement procedure other than regular non-isomorphic graphs ?

  • $\begingroup$ How tight a bound are you looking for? As you argue in the question, it can't be more than linear; but a path of lengh $n$ requires about $n/2$ iterations. $\endgroup$ – David Richerby Mar 25 '17 at 11:06
  • $\begingroup$ it can't be more than linear say $ n - c$, I am looking for largest $c$ such that for all inputs, number of iterations is $\le n - c $. $\endgroup$ – aaaa Mar 25 '17 at 12:03
  • $\begingroup$ OK, but you might've already done that. I've not managed to think of anything that takes more than $n/2$. $\endgroup$ – David Richerby Mar 25 '17 at 12:38
  • $\begingroup$ This seems to be a research-level question, and it isn't getting answered on Computer Science, so I am migrating to Theoretical Computer Science at the asker's request. $\endgroup$ – Gilles 'SO- stop being evil' Apr 9 '17 at 10:28
  • 1
    $\begingroup$ The most comprehensive discussion seems to be arxiv.org/abs/1509.08251 but the authors focus on the total time, not the number of rounds. The class of example graphs $G_k$ might be useful. $\endgroup$ – András Salamon Apr 10 '17 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.