Re: Need Graph Isomorphism Algorithm De-bunked


"Sebastian Gottschalk" <seppi@xxxxxxxxx> wrote in message
news:4nif23Fa857oU1@xxxxxxxxxxxxxxxxx
Bill Cox wrote:

I thought this forum

This is no forum, this is Usenet.

I've written a graph isomorphism program that determines if two graphs
are isomorphic. It runs in O(N^3).

Since graph isomorphism is a long studied problem with (AFAIK) no known
polynomial time solution, my algorithm is more than likely flawed. Any
help finding the flaws would be appreciated! The web site is

http://www.billrocks.org/ideas

Your problem is the hash - what happens if, by very low chance, you
encounter a collision? Then the algorithm fails.

Actually, that does not appear to be a fatal problem. Suppose you replace
the hashes with universal hashes (based on a randomly selected key). Then,
this is a randomized algorithm that has a probability of failing (that is,
reporting two different graphs as being identical), but as long as this
probability is bounded away from 1, this would show the graph isomorphism
problem is in coRP, which (AFAIK) is not currently known.

Of course, you'd still need to prove that a) the probability of a collision
somewhere in the run of the algorithm is bounded away from 1, and b) if
there isn't a collision, the algorithm always reports the correct result.
(a) appears to be fairly straightforward (given a few algorithm tweaks), (b)
looks like it's the tricky point.

--
poncho


.

Relevant Pages

  • Re: Algorithm to determine matrix similarity
    ... such an S would be an algorithm to decide whether ... The OP's problem subsumes the graph isomorphism ... 2-colored undirected graphs (with self-edges). ... matrices amounts to classifying the nodes by ...
    (sci.math)
  • Re: Is graph isomorphism in P?
    ... to do the sorts of things that have been stated ... "Is graph isomorphism in P?"... ... whether the algorithm works or not. ...
    (sci.math)
  • Re: (Probably flawed) Polynomial time Graph Isomorphism
    ... Bill Cox wrote: ... significant progress analyzing this algorithm. ... Since graph isomorphism is a long studied problem with no known ...
    (comp.theory)
  • Re: Text Mining Issue
    ... you are using Naive Bayes classification. ... AFAIK MS NB ... algorithm adds some prior knowledge to the model, i.e. adds cases for low or ...
    (microsoft.public.sqlserver.datamining)
  • Re: Any obvious reason for sudden drop in PR?
    ... Fabio wrote: ... update you will see a 4 again AFAIK ... It is if nobody links to it, Google doesn't find it, and I think that the ... "old link update" algorithm is very very slow. ...
    (alt.internet.search-engines)