Re: Need Graph Isomorphism Algorithm De-bunked

fgrieu wrote:
On the positive side, **IF** the algorithm works save for
an accidental hash collision, I think we can get rid of any
possibility of collision, and still be in polynomial time
(as Mike conjectured then retracted).
I replace the cryptographic hash with ordering and concatenation
of input (each ceil(log2(n)) bits), giving a longhash.
After the step reading "update each vertex's hash value", I sort
the N longhashes, then output each longhash (with length prefix),
then replace each unique value with its index among unique values,
which fits ceil(log2(n)) bits. This avoids exponential explosion.
The result of each "hash iteration" is the concatenation of
all outputs during this "hash iteration", and the last longhash.
The rest is unchanged.

Last night I thought I understood what you are suggesting, and if the algorithm works, it would put graph isomorphism into P, not just RP. This morning I'm doubtful.

First, do I understand the what you suggest? Is it
0. All values are in the range 0..n-1.
1. Assign the special node the value 1. Assign all the other nodes the value 0.
2. For each node, assign a bit string which is its value represented as a bit string of length ceil(lg2(n)) followed by the bit strings of that length representing its neighbors' values in sorted order.
3. Make a list of all the bit strings assigned in this iteration, with duplicates removed. Sort the list (Regard a shorter string as strictly less than any longer string.). Assign each node a new value which is a perfect hash of its bit string in this iteration, namely the ordinal number of its bit string in the sorted list.
4. Loop back to step 2 some number of times (N? N/4?).
5. Record each node's value assigned by the most recent iteration of step 3.
6. Repeat steps 1 through 5 once with each node as the special node.
7. Assign each node a final bit string of length n*ceil(lg2(n)) consisting of the bit string representing its recorded value when it was special followed by its sorted recorded values when it was not special.
8. Compare the (sorted) list of bit strings assigned in step 7 for one graph with those assigned to another graph.

I think the perfect hashing throws away too much data. I suspect that the values of the CS hashes generated by previous versions of the algorithm may differ in ways that allow the CS-hash method to distinguish graphs that the perfect-hash method regards as isomorphic. But I haven't looked for an example yet.

--Mike Amling
.

Relevant Pages

  • Re: How to write a diff in VB6 for comparing two xml files?
    ... No, the best you could do is to read both into string and use StrCompbut it's inefficient and, but using the hash ... Private Declare Function CryptAcquireContext Lib "AdvAPI32.dll" Alias _ ... Dim HashAAs Byte, HashLenA As Long ...
    (microsoft.public.vb.general.discussion)
  • Re: something like switch in c
    ... >> straightforward string comparisions. ... > inner table size and/or add symbols to expand the hash. ... It all depends on the empirical pattern of the actual keys. ... The value of the random number generator is UNCHANGED on ...
    (comp.programming)
  • Re: How to make PKCS#7 signature using CryptoAPI?
    ... Those MSDN samples hash a string PLUS the null byte (so that it ... I tried your sample and had no problem verifying with openssl (after I added ... functions (including CryptSignMessage). ...
    (microsoft.public.platformsdk.security)
  • Re: How to make PKCS#7 signature using CryptoAPI?
    ... "Mitch Gallant" wrote: ... Those MSDN samples hash a string PLUS the null byte (so that it ... functions (including CryptSignMessage). ...
    (microsoft.public.platformsdk.security)
  • Re: Base36
    ... static string tokens = ... But - I don't think you want all those silly characters in the product key. ... I should be able to recalc the hash at the client ... > conversion to long so I can pass each long to the BaseXX converter to get ...
    (microsoft.public.dotnet.languages.csharp)