Re: Need Graph Isomorphism Algorithm De-bunked

I don't understand that there's a problem with auto-morphism. If two
nodes end up with the same hash, then the graph with those nodes
exchanged is isomorphic to the original graph, which is as it should be.
And the nodes of any other graph isomorphic to that graph will generate
the same node hash values with the same duplicate values.

--Mike Amling

Automorphism isn't a problem if I'm only trying to detect that graphs
are isomorphic. However, if I want to report the node correspondence,
the automorphic nodes have to be resolved. For example two simple
isomorphic rings of nodes will have several possible valid mappings
(about 2*(N-1)). All the nodes will wind up with the same label, but I
can't just make a random mapping and expect it to be valid. What I do
in this case is just assign the first pair of nodes, and then do
another hash iteration with the assigned nodes acting as start-nodes.
In the case of the rings, the rest of the nodes will then all get
unique hash values, so they can be matched up correctly. This seems to
work so far.

Being able to report the correspondence is important, both in the
real-world, and to detect counter-examples that cause the algorithm to
fail. Once the actual isomorphism mapping is reported, I do a simple
check to see if it's valid. I'm hoping to catch a counter example this
way, but I'm still dealing with bugs, and it's unfortunate, but true
that I have other work to do!

One possible result from this effort so far... Even if graph
isomorphism isn't in P, I think it's not a good idea to use exact graph
isomorphism for cryptography. It seems VERY hard to generate a pair of
graphs that are difficult to match! Any ideas for generating difficult
to match graphs would be appreciated!

.

Relevant Pages

  • Re: Help with Diagonal subgroup problem
    ... >and N could fill up the entire graph and equal G. ... the "graph" of the isomorphism. ... M is identified with the subgroup of G; ... --- Calvin ...
    (sci.math)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... exchanged is isomorphic to the original graph, which is as it should be. ... the same node hash values with the same duplicate values. ... Once the actual isomorphism mapping is reported, ... I'm worried about the classic Zero Knowledge proof a Hamiltonian circuit. ...
    (sci.crypt)
  • Re: copyright for combinatorial entities
    ... graph, if for no other reason than doing so would fly in the ... face of the reason for having copyright in the first place, ... blocking the publication of an adjacency matrix ... isomorphism is another issue. ...
    (sci.math)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... graph and Hamiltonian cycle problems,, Victor ... If graph isomorphism is in RP (as ... about the circuit in G by being shown the circuit in H. ... the prover either sends keys to unlock only edges that form a Hamiltonian circuit or sends the permutation of the nodes that constitutes the isomorphism and keys to unlock all edges. ...
    (sci.crypt)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... The proof that isomorphic graphs give identical hash, ... We'll be running this version of the algorithm, ... [values of each node in sorted order ]. ... value'@the same for graph G'. ...
    (sci.crypt)