Re: Is graph isomorphism in P?

On Jul 19, 2:21 pm, Fra <fra.cristi...@xxxxxxxxx> wrote:
Hi all,

you are invited to see the results of my research about
graph isomorphism problem here:

http://isoproblem.freeforums.org

Thanks a lot

Fra states: "In this site you will not find the algorithm or any
explanation of it, I wish to use this forum in order to place in it
hard istances of the MI problem that otherwise would require a
prohibitively computation-time to solve it." This makes it hard for
people to (1) find two graphs which are isomorphic, for which the
algorithm fails to find the isomorphism, or (2) verify that the
algorithm runs in polynomial time.

Fra invites people to post graphs to test his isomorphism program,
adding: "please not post matrices with more than 350/400 rows, this
because I've limited computing resources (only my laptop with 1,2 Gb
RAM on AMD Athlon 64) to run the algorithm." Well, Fra, the
isomorphism problem, where you only look at graphs with at most 400
vertices, can be solved in CONSTANT TIME.

If Fra is afraid that he's found a polynomial-time algorithm for
testing graph isomorphism and someone will steal it, he should realize
that posting it to Usenet (where the post will be dated) and/or
sending himself a copy of that algorithm as a letter in the mail
("poor man's copyright") are both ways to later prove that he did come
up with the algorithm first.

Lastly, he says: "During my research I've found that is possible to
give an algebraic characterization for every matrix involved in the MI
problem and I've used it to solve the problem with a P-time algorithm
(implemented in java)." This Java code should definitely be made
public.

--- Christopher Heckman

.

Relevant Pages

  • 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: Is graph isomorphism in P?
    ... algorithm runs in polynomial time. ... Fra invites people to post graphs to test his isomorphism program, ... Anyway, I've no problem to solve 600x600 or 1000x1000 MI istances, ...
    (sci.math)
  • Re: (Probably flawed) Polynomial time Graph Isomorphism
    ... On random input graphs graph isomorphism ... Note that testing degree sequences is a deterministic algorithm. ... The problem here is the algorithm relies on a hash function, ...
    (comp.theory)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... Bill Cox algorithm that you verified up to 8 nodes, ... not in your implementation) is in my rendering of Bill Cox's ... proved the graphs are not isomorphic. ... graphs are equal iff you have established an isomorphism between the two graphs, and to do that you have to cope with Bill Cox's automorphism issue. ...
    (sci.crypt)
  • 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)