Re: Is graph isomorphism in P?

On 20 Lug, 06:30, Proginoskes <CCHeck...@xxxxxxxxx> wrote:
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.

(1)in this page:
http://isoproblem.freeforums.org/viewtopic.php?t=5

I've suggested how to generate random adjacency matrices
of bipartite graph (I means undirected graph). It requires
only bit of seconds with octave; the only difficulty is
to obtain matrices with no duplicate rows.
This problem can be avoided increasing the maximum numbers
of '1' in each row in this octave instruction:
from:
M=round(randerr(300,300,3));
to
M=round(randerr(300,300,5));

for the (2)'s answer see below.

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.

Oh yes?! Please let me know how to find an isomorphism for this MI
istance:
http://isoproblem.freeforums.org/viewtopic.php?t=19
in CONSTANT TIME.

I never meant that my algoritm can be solve GI problem
with at most 400 vertices; I mean that: having only
1,2Gb of Ram, because algorithm is based on exploration of
mathematical objects whose demanded of memory icreases
with vertices increasing, if I try to solve an MI istance
for a 2000x2000 I'll get "Could not reserve enough space for
object heap" by the java virtual machine.

Anyway, I've no problem to solve 600x600 or 1000x1000 MI istances,
let me some hours and I will post here:
http://isoproblem.freeforums.org/viewforum.php?f=1
also a 600x600 MI problem on adjacency matrix of
bipartite graphs.

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.

Sorry, but this is your personal interpretation.
The idea is that in this phase I wish to test the algorithm for
"hard istances of the MI problem that otherwise would require a
prohibitively computation-time to solve it". (it is written here:
http://isoproblem.freeforums.org/viewtopic.php?t=5 )
This indirectly can proof the polinomial-time nature of the
algorithm.
(I.E. if for a 600x600 bipartite graph the world's fastest isomorphism
testing program, that is Nauty, will need of thousand of years and I
will give you an isomorphism in 6/7 hours, I think that this is really
significant!)


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

At the end of test phase, if the algorthim never fails, I'll publish
all.

Fra

.

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: (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: Is graph isomorphism in P?
    ... "In this site you will not find the algorithm or any ... algorithm fails to find the isomorphism, ... Fra invites people to post graphs to test his isomorphism program, ...
    (sci.math)
  • 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)