Re: New algorithm for the isomorphism of graphs

On Jul 27, 1:54 pm, mimouni <mimouni.moha...@xxxxxxxxx> wrote:
4) Whereas even in the case of two graphs biparti, nonplanar. One can
always make a reduction for arrived obtained either from the trees or
of the planar ones.
This looks like it says that if you can find an algorithm for the case
of two trees, or the case of two planar graphs, then you can solve the
isomorphism problem in general. I seriously doubt that this is true,
since the Graph Isomorphism problem would be known to be in P.

Ok, if G is isomorphism with G' one can cut the graph of pieces, which
makes the algorithm, the vertices of G which of which in level I must
be isomorphism at the vertices of G' which are in level I. thus in the
case of the graphs biparti the algorithm crosses (I did not find
another word) in several graphs biparti...

But if Level I (in G and G') has k vertices, then you still need to
find out how the vertices in Level I of G match up with the vertices
in Level I of G', and there can still be an non-polynomial number of
ways for this to happen (even if k is something like ln(n)). (Think of
a graph with large girth, where the neighborhood, 2nd neighborhood,
etc., up to the 10th neighborhood have no cycles in them, only
branching out.)

Another thing, so in general one has two graphs G and G' isomorphisms,
and F the function of isomorphs and F (s) =s', one can obtained two
new graphs isomorphisms one removes s in G and s' in G'. And one can
the same operation for the edges: F (a,b) = a',b' and if one removes
in G the edge a, b (not the vertices a and b) and idem for G' the two
new graphs are always isomorphisms.

Then the problem of isomorphisms of the graphs biparti is reduced to
the problem planar graphs biparti, or trees and these two cases are
polynomial.

Once again, *if you remove the correct edges*, this will work, but you
have to have a "paranoid" attitude towards proving the running time is
polynomial. If your graph has m edges, and let's say that m = 4*n,
then you have to remove (at least) n edges to make the graph planar.
If you don't know which edge to remove, you have to try all
possibilities, and with the "paranoid" attitude, the edges that work
will be the last case on the list of all possible sets of edges. (Or:
the graphs might not be isomorphic, which you would only find out by
trying all the possibilities.)

So suppose you have 4*n edges, and you want to choose n of them to
remove. There are C(4*n,n) ways to do this (where C is the binomial
coefficient), which is already exponential in n. (In fact, it grows
faster than 9^n.) This is how many times you have to run the planarity
isomorphism algorithm.

It all keeps coming back to the question that no one on this planet
(evidently) can answer: How do you find vertices (or edges), which
correspond in some isomorphism? Considering all possibilities, or
"getting lucky" are not options.

--- Christopher Heckman

.

Relevant Pages

  • Re: New algorithm for the isomorphism of graphs
    ... of two trees, or the case of two planar graphs, then you can solve the ... since the Graph Isomorphism problem would be known to be in P. ...
    (sci.math)
  • Re: New algorithm for the isomorphism of graphs
    ... method to obtain new bipartis, until obtaining planar bipartis. ... to find among the graphs bipartis, ... Isomorphism between two bipartis regular will be obtained one ...
    (sci.math)
  • Re: New algorithm for the isomorphism of graphs
    ... method to obtain new bipartis, until obtaining planar bipartis. ... to find among the graphs bipartis, ... Isomorphism between two bipartis regular will be obtained one ...
    (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)