Re: Need Graph Isomorphism Algorithm De-bunked

\> > 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.

Thanks for the reply!

This is an interesting point, and please keep trying to find more flaws
(which are most likely there). I think is a complication, but not a
killer. Given two truly random graphs of any significant size (say, N
100) with the same number of nodes and edges, I agree that the algorithm is far more likely to report a false positive than a correct result.

However, I've got a great function that is perfect for comparing large
random graphs:

bool compareRandomLargeGraphs(Graph G1, Graph G2)
{
return false;
}

Two truly random graphs of any significant size will realistically
never match.

There are plenty of algorithms that CAN fail, but realistically wont.
RSA is a good example. It tests primeness of it's two secret prime
numbers using a probabilistic algorithm. The important thing (I think)
with these kinds of algorithms is choosing how much risk we can live
with. The prototype code I wrote uses all 32-bit numbers, which makes
collisions fairly likely. In the real world, we'd need hash functions
of 64-bits or more. I begin to be comfortable somewhere around 256
bits. Even so, given two truly random graphs, it's more likely that
we'll find a collisions, than it is for two random graphs of any
significant size to actually be isomorphic.

As a real-world example (the one that got me thinking about this),
consider LVS (layout versus schematic) algorithms. In this case, we
try to show that two graphs representing circuits are the same. If the
user made no mistakes in implementing his circuit in silicon, the
graphs will match. If the algorithm says they don't match, then
there's an error the user has to fix. If the algorithm says the graphs
match, and if our hash function is good and uses many bits (say 256),
then the probability of being wrong should be something like 1/(2^256).
I can live with that. Also, we can easily check the graph
isomorphism, and I already included such a check in the code.

Since detecting a failure is easy, the algorithm could be enhanced to
re-randomize the input graphs, and try again. The chance of running
into yet another collision becomes vanishingly small.

.

Relevant Pages

  • Re: Sean PItman and nested hierarchy
    ... if God created life then the patterns in the ... the concept of "uniform probability distribution" is well-defined. ... Since the vast majority of the graphs ... Yes, it can, depending on the algorithm used. ...
    (talk.origins)
  • Re: Sean PItman and nested hierarchy
    ... the concept of "uniform probability distribution" is well-defined. ... Since the vast majority of the graphs ... Yes, it can, depending on the algorithm used. ... Separate creation can produce any pattern whatsoever, including a nested hierarchy. ...
    (talk.origins)
  • Re: Is graph isomorphism in P?
    ... algorithm runs in polynomial time. ... graphs which are "pathological", so most of the time, you can solve NP- ... This is also why the average running time is not a good measure; ... isomorphism problem, where you only look at graphs with at most 400 ...
    (sci.math)
  • Re: Sean PItman and nested hierarchy
    ... if God created life then the patterns in the ... Since the vast majority of the graphs ... Yes, it can, depending on the algorithm used. ... create a tangled loop in the graph. ...
    (talk.origins)
  • Re: Is graph isomorphism in P?
    ... time you can find its clique size in polynomial time. ... graphs which are "pathological", so most of the time, you can solve NP- ... who works on Graph Isomorphism ... Especially in this sense I'm testing my algorithm. ...
    (sci.math)