NetNews Usenet Archive 1992 #31/NN_1992_31.iso/spool/comp/theory/2775

Internet Message Format | 1993-01-01 | 5.5 KB

Path: sparky!uunet!munnari.oz.au!manuel.anu.edu.au!tyl.anu.edu.au!not-for-mail
From: [e-mail] (Brendan McKay)
Newsgroups: comp.theory
Subject: Re: randomized-hash graph-iso algorithm - more discussion
Date: 1 Jan 1993 16:24:02 +1100
Organization: Australian National University
Lines: 120
Distribution: inet
Message-ID: <[e-mail]>
References: <[e-mail]>
NNTP-Posting-Host: 150.203.23.70

[e-mail] (William Naylor) writes:
[...William's article heavily editted to save space...]

>  2)  [e-mail] (Brendan McKay) claims that P algorithms for
>      graph-iso are already known for

>      a)  graphs with bounded vertex degree
>      b)  graphs of bounded genus

The key papers on this appeared in the Proceedings of the Foundations
of Computer Science conferences, around 1980-3.  The authors are
Babai, Luks, Miller, Filotti, Meyer and a few others.  A common
generalisation of (a) and (b) can be found in

G. Miller, Information and Control 56 (1983) 1-20.

>  3)  [e-mail] (Brendan McKay) claims that my algorithm does
>      not work properly on large classes of graphs which are of interest in
>      various mathematical work.  If what he says is true, this
>      weakens my argument in favor of the Gismondi-Swart strategy.

>      Clearly, the algorithm I gave does not work on graphs where
>      all vertices have the same degree.  This problem can be easily patched
>      (see below).

It also doesn't work for many interesting graphs where the degrees are
not all the same.  For example, take a regular graph and subdivide
each edge with a new vertex.  It won't work for that either.
Other more direct examples exist too; see below.

>      Can somebody out there point out some classes of graphs
>      for which my algorithm usually fails, which cannot be easily patched?

I will send some by e-mail.

>  4)  My original argument still seems correct.


>====================================================================
>                      MY ORIGINAL POST
>====================================================================

[deleted by bdm]

>====================================================================
>      DISCUSSION of a POST by [e-mail] (Brendan McKay)
>====================================================================

>In article 5857 of comp.theory, [e-mail] (Brendan McKay) wrote
>a detailed response to my post.  I have attempted to clarify several
>points with him by e-mail, but I have received no reply.  Therefore,
>I must discuss his post without benefit of discussion with him.

Sorry.

>In article 5857 of comp.theory, [e-mail] (Brendan McKay) writes:

>>>The relevance of my algorithm to the discussion of the paper of
>>>Swart et. al. is this:
>>>the existence of this successful randomized algorithm for graph isomorphism,

>>There is no evidence for such an algorithm.  Yours only works for
>>restricted classes of graphs.

>The original algorithm I presented fails to distinguish graphs of the
>same order with vertices all having the same degree.  This is
>a very small fraction of all possible graphs.  Anyway, this problem can
>be patched (see below).

>Does anybody out there see any classes of graphs that can fool my
>(patched) algorithm?

Yes, there are many.   I will send you some by e-mail.
The most natural examples are strongly-regular graphs and the
incidence graphs of balanced designs.  The latter are not
necessarily regular.  These are standard test-cases for
isomorphism programs.  I have some others, maybe even harder.

>>Methods that are as strong or stronger date back to the 1960s.
>>Modern approaches supplement invariant computations with backtracking.
>>Several programs exist that can handle thousands of vertices
>>(one is mine, enquiries welcome).

>Could somebody post some references to these algorithms?

One early algorithm was due to Corneil and Gotlieb.  (Sorry, I'm
at home and can't look up the reference.)  Their algorithm is
based on a conjecture later proved by false by Rudi Mathon.
Even though it is deterministic, it is stronger than even your
patched algorithm in the sense that if their's fails, yours
will fail for every hash function.  The reason is this:

Take a graph G and a vertex v.  Let V1,V2,...,Vk be the coarsest
partition of the vertex set of G such that
(i)  V1 = {v}
(ii) If C is any cell, and x,y are two vertices in the same
     cell (possibly C), then x and y are adjacent to the same
     number of vertices in C.
Now define the "quotient matrix" M of order k*k:
     M[i,j] = number of y in Vj adjacent to each fixed x in Vi.
(I didn't specify the order of the cells V2,...,Vk, but these
can easily be put into a canonical order using M.  Think about it.)
Now, the value your patched algorithm gets for this particular v
distingushed depends only on M and not on the finer structure
of G.  Any two graphs which have the same set of M's (one per v)
will be indistinguisable by your method.  As an example, any
strongly regular graph was the same M for every vertex and
that M only depends on the graph parameters.

Advertisement:  I distribute a deterministic algorithm called nauty.
It computes canonical labellings and generators for the automorphism
group.  I think it's pretty good.  It is free subject to weak
conditions of use.  For further information, send a note to me
that includes your complete (paper and electronic) address.

>My (unpatched) program can work on graphs with 50,000 vertices in 5-10 minutes.

>Will Naylor               net:  [e-mail]

Brendan.