Skip to content

An Approach to Graph Isomorphism?

May 4, 2009


Graph isomorphism and classic invariant theory

images2

David Hilbert is one the greatest mathematicians of all times, but you knew that. He solved hard open problems, he unified fields, and he created his famous “program” for the foundations of mathematics. The latter was essentially destroyed by Gödel Incompleteness Theorem.

Today I want to focus on an area he made important contributions to, and is related to one of his problems from his famous list of {23} open questions. He presented his list at the international mathematics meeting in Paris in 1900. His list of problems have been extremely influential, and has lead to great work by many mathematicians. Hilbert was generally an excellent selector of what problems were important and could be solved.

Some of the problems were solved quickly, some were solved decades later, some are still open, and some are “fuzzier” and may never really be solved. Others were solved, then errors were found in their proofs decades later, and the problems were re-solved. See this for a wonderful treatment of the problems and the people who have worked on them.

In the category of problems that were solved quickly is Hilbert’s question about tetrahedra: his third problem. This problem was solved fairly quickly: Ron Graham once told me this problem was so “easy” that the solver, Max Dehn, found it during Hilbert’s talk, but he did miss the statements of the next two problems. Ron is slightly exaggerating the situtation, but not by much. While the proof is clever, it is not probably as hard as most of the rest of the Hilbert problems.

Today I want to talk about graph isomorphism and its relationship to classic invariant theory. Invariant theory is an area that Hilbert made major contributions to and is related to one of his problems, the fourteenth. This post is based on work that I am doing with one of my graduate students, Farbod Shokrieh, and with Ken Regan.

Graph Isomorphism

Graph Isomorphism (GI) is one of the most famous problems in complexity theory and mathematics. The appeal of this problem is that it sounds so approachable: it is just about undirected graphs, after-all. But it is one of the great “diseases,” that is it is one of those easy to state problems that has bent a little over the years, but refuses to break. There are some quite pretty results known about GI, but still it is unknown whether GI is in polynomial time. We do not even know if GI is in {\mathsf{P/poly}}, i.e. does it have polynomial size circuits, nor do we know if it is in {\mathsf{NP}\cap\mathsf{co} \text{--} \mathsf{NP}}. We owe Laszlo Babai the great insight into creating the new class {\mathsf{AM} \supseteq \mathsf{NP}}, so at at least we have that GI is in {\mathsf{NP}\cap \mathsf{co} \text{--} \mathsf{AM}}.

Many special cases are known to be easy: trees, planar graphs, random graphs with high probability, and constant degree graphs: the latter is a beautiful result of Eugene Luks. There are also many equivalent problems and related results, but I will not attempt to give a complete list of all the known results.

My goal today is to outline a connection between GI and some interesting questions from classic mathematics. In the best case, it could lead to real progress on GI. In any event the idea raises questions and potential applications that beg to be explored further.

Bipartite Graphs

Instead of the general GI problem we will focus on another GI complete problem. The problem is given two {0}{1} {n \times n} matrices {G} and {H} are there two permutations matrices {P} and {Q} so that

\displaystyle  P G Q = H.

We claim that this problem is equivalent to GI problem. We will call this problem the restricted bipartite graph isomorphism (RBGI) problem.

The rationale for the name is that essentially it is a special case of the bipartite graph isomorphism problem. The only extra restrictions we have added is that we:

  1. We require the two color sets to have the same cardinality;
  2. We insist that the isomorphism preserve the colors.

It is easy to see that these leave the problem GI complete, since it is an old result that GI can be reduced to the bipartite case. However, it is convenient to have the more restricted problem.

For the remainder of this post we will use the matrix representation of graphs. Thus, when say that {G} is a graph, we simply mean that {G} is a {n \times n} {0}{1} matrix. Thus, the graph {G} is isomorphic to {H} provided there are permutation matrices {P} and {Q} so that

\displaystyle  P G Q = H.

Invariant Theory for the Symmetric Group

A central problem of invariant theory is given a finite group {G} that acts on {X=(x_{1},\dots,x_{n})} what polynomials are invariant under the group? A polynomial {f(X)} is invariant under a group {G}, provided for all {\pi \in G},

\displaystyle  f(X) = f(\pi X).

When the group {G} is the full symmetric group, {S_{n}} this is simply the class of symmetric polynomials. Thus,

\displaystyle  x_{1} + x_{2} + \dots + x_{n}

is invariant, while

\displaystyle  x_{1} - x_{2} + \dots + x_{n}

is not: a permutation that exchanges {x_{1}} and {x_{2}} changes the polynomial.

For any finite group {G} the polynomials invariant under {G} form an algebra. That is just a fancy way of saying that the sum and product of two invariant polynomials is still invariant. The goal is to describe this algebra in as succinct a manner as possible. Let see how this is done, first, in the basic case of the full symmetric group.

The {k^{th}} elementary symmetric functions {e_{k}(x_{1},\dots,x_{n})} are the sum of all distinct products of {k} distinct variables:

\displaystyle e_{0}(x_{1},\dots,x_{n}) = 1

\displaystyle e_{1}(x_{1},\dots,x_{n}) = x_{1} + x_{2} + \dots + x_{n}

\displaystyle  \vdots

\displaystyle e_{n}(x_{1},\dots,x_{n}) = x_{1}x_{2}\cdots x_{n}

The elementary function satisfy two basic theorems. First, they generate the algebra of all symmetric polynomials and second they are easy to compute.

Theorem: If {f(X)} is a symmetric polynomial, then there is a another polynomial {g(Y)} so that

\displaystyle  f(X) = g(e_{1}(x),\dots,e_{n}(x)).

This can be proved by an induction on the number of variables. See this for details. Thus, the elementary symmetric functions generate, as an algebra, all the symmetric polynomials. Note, they do not generate all symmetric polynomials as a vector space: just consider a very high degree symmetric polynomial, it clearly will not be a linear combination of the elementary functions.

Theorem: Given {x_{1}, \dots, x_{n}} there is an algorithm that computes all {e_{k}} for all {k=1,\dots,n} in polynomial time.

The proof of this theorem uses the following simple insight. Let

\displaystyle  f(t) = (t-x_{1}) (t-x_{2}) \dots (t-x_{n}).

Expanding this out gives,

\displaystyle  f(t) = t^{n} + (-1)^{1}e_{1}t^{n-1} + (-1)^{2}e_{2}t^{n-2} + \dots + (-1)^{n}e_{n}.

Thus given values {x_{1}, \dots, x_{n}} we can use Lagrange interpolation to obtain the coefficients of the resulting single-variable polynomial, which give us the desired evaluations of every elementary function.

Invariant Theory for Bipartite Graphs

Let

\displaystyle  X = (x_{1,1},x_{1,2}, \dots, x_{n,n})

be the general vector that stands for a general {n \times n} matrix. The group that we are interested in is not the full symmetric group {S_{n^{2}}}. Instead we need to use the subgroup that is isomorphic to {S_{n} \times S_{n}}. The action of a group element {(r,c)} is to permute the rows of {X} by {r} and then the columns by {c}. Let’s denote the group by {{\cal B}_{n}}, or just {\cal B} when the subscript is clear. We are interested in polynomials that are invariant under this group.

Note, because the row and column permutations are independent we the invariant theory is based on a direct product of symmetric groups. Otherwise, the action would be more complex.

What we hope is that there is something like the basis of elementary functions for the polynomials invariant under {\cal B}. We need there to be polynomials

\displaystyle \beta_{1}(X), \dots, \beta_{m}(X)

that are {{\cal B}_{n}} invariant and they generate the algebra of all {{\cal B}_{n}} invariant polynomials. And further:

  1. The number of the polynomials {m} is bounded by {n^{O(1)}}.
  2. Each polynomial {\beta_{k}(X)} has a straight-line arithmetic computation that is at most {n^{O(1)}} long.

Let us call these assumptions {\Gamma}. Note, the analogous assumptions are true for the symmetric polynomials. Classic results from invariant theory, I believe, show that at least a weaker result is easy. The assumption {\Gamma} is true without the restriction on the number or the complexity of the polynomials {\beta_{k}(X)}. As usual we in complexity theory need more.

Invariant Theory and GI

The reason we have raised the assumption {\Gamma} is that it is enough to make a breakthrough on GI.

Theorem: Suppose that {\Gamma} is true, then GI is in {\mathsf{P/poly}}.

The algorithm is very simple. Suppose that {G} and {H} are graphs. Then, for each {k}, check whether or not

\displaystyle  \beta_{k}(G) = \beta_{k}(H).

If this fails for some {k}, then clearly {G} cannot be isomorphic to {H}. If on the other hand, this holds for all {k}, then we claim that {G} must be isomorphic to {H}. Note, the algorithm can be done by a circuit of polynomial size by the assumption {\Gamma}.

It only remains to show that the algorithm is correct. The key case is where {G} and {H} satisfy the above test for all {k}, yet are not isomorphic. We will show that is impossible.

We need some definitions first. Let {A} be a graph. Define the following function:

\displaystyle  F(A,x_{1,1},x_{1,2}, \dots, x_{n,n}) = \prod_{A_{ij}=1} x_{i,j} \times \prod_{A_{ij}=0} (1-x_{i,j}).

Lemma: Consider {F(A,M)} as a polynomial in the matrix {M}. Then, {F(A,A)=1} and {F(A,B)=0} for any {B} that is not equal to {A}.

Proof: The value of {F(A,A)} is equal to

\displaystyle  \prod_{A_{ij}=1} A_{i,j} \times \prod_{A_{ij}=0} (1-A_{i,j})

which is clearly {1}. The value of The value of {F(A,B)} is equal to

\displaystyle  \prod_{A_{ij}=1} B_{i,j} \times \prod_{A_{ij}=0} (1-B_{i,j}).

Since {A} and {B} are different, there is a pair of indices {r,c} so that either

\displaystyle  A_{rc} = 1 \text { and } B_{rc} = 0

or

\displaystyle  A_{rc} = 0 \text { and } B_{rc} = 1.

In the either case the product is clearly {0}. \Box

Let {X = (x_{1,1},x_{1,2}, \dots, x_{n,n})}. Then, the following is the symmetric form of the polynomial {f}:

\displaystyle  f^{{\cal B}}(X) = \sum_{\pi \in {\cal B}} f(\pi X).

Finally, for a graph {G}, let {|\mathsf{Aut}(G)|} be the number of elements \pi = (P,Q) of {\cal B} such that

\displaystyle  \pi G = P G Q = G.

Then,

Lemma: Suppose that {G} and {H} are isomorphic graphs, then {F^{\cal B}(G,H) = |\mathsf{Aut}(G)|}. Suppose that {G} and {H} are not isomorphic graphs, then {F^{\cal B}(G,H) = 0}.

Proof: The key is if they are not isomorphic then the sum is over all zero’s. In the case they are isomorphic, it sums over all possible {P} and {Q} so that {PGQ=G}. \Box

This lemma shows that the algorithm works as claimed. For suppose that {G} and {H} are not isomorphic. By assumption {\beta_{k}(G) = \beta_{k}(H)} for all {k}. Since the polynomials {\beta_{k}(X)} generate the algebra of all {\cal B} invariant polynomials, it must be the case that {F^{\cal B}(G,G) = F^{\cal B}(G,H)}. This is a contradiction since,

\displaystyle  F^{\cal B}(G,G) = |\mathsf{Aut}(G)| \ge 1

and

\displaystyle  F^{\cal B}(G,H) = 0.

Open Problems

The main open problem is to see if this approach can work. We need, of course, to understand the assumption {\Gamma}. Note, if somehow we proved that GI did not have polynomial size circuits, then we would show something non-trivial about the action of {\cal B}. Either there would be a super polynomial number of generators or the generators must have large complexity.

Also even if {\Gamma} fails, there are weaker versions that would say something non-trivial about GI. For example, suppose {\Gamma} had an exponential number of generators {\beta_{k}(X)}, but each still had polynomial complexity. Then, we would get that GI is in {\mathsf{NP}\cap\mathsf{co} \text{--} \mathsf{NP}}. The latter would require that we could efficiently go from {k} to the circuit for {\beta_{k}}.

62 Comments leave one →
  1. May 4, 2009 11:11 am

    A similar approach has been tried by N.Thiery http://arxiv.org/abs/0812.3082
    He considered the invariants of the action of S_m on the ring \mathbb{C}[x_{12},\dots,x_{m-1,m}]. This is probably as bad, in terms of the complexity of a generating set, as the one you propose…

    • rjlipton permalink*
      May 4, 2009 1:24 pm

      Thanks for pointing this out..rjlipton

  2. Anon 1 permalink
    May 4, 2009 11:25 am

    “The assumption {\Gamma} is true without the restriction on the number or the complexity of the polynomials {\beta_{k}(X)}.”

    Isn’t the assumption $\Gamma$ *only* about the number and complexity of the polynomials $\beta_{k}$? Did you mean to write something else, or am I missing something?

    • rjlipton permalink*
      May 4, 2009 1:28 pm

      Yes, sorry for the confusion.

  3. kintali permalink
    May 4, 2009 12:41 pm

    I was trying to discuss the following for quite sometime. I think this post is the best place to discuss.

    I see a lot of effort in trying to find a polynomial-time algorithm for GI. We should also look at the possibility that GI is not in P, and try to prove something like the following :

    Conjecture : If P is not equal to NP, then GI is neither NP-complete nor in P.

    Correct me if I am missing something. It is motivated by Ladner’s theorem and the fact that GI is unlikely to be NP-complete.

    On a related note, are there any natural problems (say A) that fit the above conjecture i.e., if P is not equal to NP, then A is neither NP-complete nor in P.

    • rjlipton permalink*
      May 4, 2009 1:27 pm

      The other obvious choice might be factoring. I think your idea is interesting and I have thought about the general idea too.

  4. Pascal Koiran permalink
    May 5, 2009 1:56 am

    To kintali : I think it’s known that GI cannot be NP-complete unless the polynomial hierarchy collaspses.
    So this problem could be in P, or could at worst be of intermediate complexity (like in Ladner’s theorem).

    • kintali permalink
      May 5, 2009 11:50 am

      Yes ! It is known that “GI is not NP-complete unless PH collapses”. That’s why I simply said “unlikely”.

  5. May 5, 2009 9:38 am

    kintali: A 1978 paper by Dexter Kozen, A clique problem equivalent to graph isomorphism, led me to believe that the conjecture you state above is true. Further, two papers at ICALP last year, by Chen/Thurley/Weyer (Understanding the Complexity of Induced Subgraph Isomorphisms) and Bodirsky/Grohe (Non-dichotomies in constraint satisfaction complexity), can be interpreted as further hints that GI may be intermediate.

  6. May 5, 2009 4:19 pm

    Thanks, Dima, for the Thiery paper—we’ve found some related ones too.
    Thiery’s setup should be close to ours, especially when we
    reduce to the bipartite case by making a separate “Blue” copy
    of the vertex set, and replacing each edge (u,v) by (u, Blue v)
    plus (Blue u, v). And you may well be right about “badness”, since
    the nxn permanent polynomials are invariant and for n >= 3 look
    pretty basic. The question becomes, over various rings, can the
    permanent be written as a big polynomial g(Y) in “easy” invariant
    generators Y? What we are pursuing now are setups where the
    determinant equals or may in some sense “cover” the permanent.

  7. Dmytro Korduban permalink
    May 6, 2009 4:53 pm

    And what about http://arxiv.org/abs/0711.2010 ?

    • rjlipton permalink*
      May 6, 2009 5:01 pm

      I do not believe that the algorithm works.

      • Dmytro Korduban permalink
        May 6, 2009 6:00 pm

        Do you know some class of counterexamples for such heuristics? I realized that it are pretty difficult to construct; even more naive approaches are almost irrefutable on large class of graphs.

        I’m interested because I’m making test data for ICPC-style programming contests, and feel lack of strong tests for GI now. =)

      • rjlipton permalink*
        May 9, 2009 7:37 am

        The class of strongly regular graphs is a good place to start. Many methods fail on these graphs; they have only three distinct eigenvalues, for example. Look here to start.

  8. Michael Trofimov permalink
    April 3, 2010 4:51 am

    In 2005, my paper about graph isomorphism testing for computer chemistry
    tasks had been printed in http://dx.doi.org/10.1007/s11172-006-0105-6 . In this paper I described original recursive algorithm, but I had problem to estimate its complexity.
    For further investigations:

    1) this algorithm was adapted for all graphs (not only for molecular graphs);
    2) iterative version was implemented;
    3) complexity of this version is O(n^5);
    4) I’ve written new paper where I strongly proved this algorithm properties.

    The title and abstract of my paper is following:

    Polynomial Time Algorithm for Graph Isomorphism Testing.
    Michael I. Trofimov,
    email: mtrofimov AT online DROP ru
    Abstract: Earlier we introduced [12] effective recursive algorithm for graph isomorphism testing. In this paper we describe used approach and iterative modification of this algorithm, which modification has polynomial time complexity for all graphs.
    Keywords: graph isomorphism, NP-complexity, graph invariant, topological index.
    Number of pages 17.

    I had written this paper two years ago and during this time period the paper was considered in a few well-known journals. Where referees did not find any fatal error in my proof, but all the journals rejected this paper. It seems that even if somebody will strongly prove that GI is polynomial problem, then he will have no possibility to print this his result: this open problem is too important to be closed never😉

    • Michael Trofimov permalink
      April 16, 2010 1:44 am

      M.I.Trofimov, Polynomial Time Algorithm for Graph Isomorphism Testing, 2010. http://arxiv.org/abs/1004.1808v1

      • wealk permalink
        May 16, 2010 11:06 am

        Actually,O(n^5)is rather an astonishing result to believe,but I strongly hope you are right!

    • Francesco Cri permalink
      May 29, 2010 6:04 pm

      I’m sorry but all your assumptions about the rejection of your paper are reasonably wrong; Consider the following graph, i.e. place it in your developed software, and run your best algorithm.

      1-35, 1-36, 1-37, 2-35, 2-38, 2-41, 3-35, 3-39, 3-43, 4-35, 4-40, 4-42, 5-38, 5-39, 5-40, 6-36, 6-39, 6-42, 7-36, 7-40, 7-41, 8-36, 8-38, 8-43, 9-41, 9-42, 9-43, 10-37, 10-40, 10-43, 11-37, 11-38, 11-42, 12-37, 12-39, 12-41, 13-23, 13-24, 13-25, 13-26, 14-23, 14-28, 14-29, 14-30, 15-23, 15-32, 15-33, 15-34, 16-24, 16-27, 16-30, 16-33, 17-25, 17-27, 17-28, 17-34, 18-26, 18-27, 18-29, 18-32, 19-24, 19-29, 19-31, 19-34, 20-26, 20-28, 20-31, 20-33, 21-25, 21-30, 21-31, 21-32, 22-23, 22-24, 22-25, 22-26, 22-27, 22-28, 22-29, 22-30, 22-31, 22-32, 22-33, 22-34, 22-35, 22-36, 22-37, 22-38, 22-39, 22-40, 22-41, 22-42, 22-43

      P.S. use this grapsh as G1 then copy it to G2 and click the button “Renumber G2”.
      It is a counterexample that falsifies your statements.

      Best wishes

      • rjlipton permalink*
        May 29, 2010 9:10 pm

        Confused.

      • Michael Trofimov permalink
        May 30, 2010 4:36 am

        This is software bug of current version (1.1.4) of MT2GI : 1) use this graph as G1 then copy it to G2 (button “G1->G2) and click the button “Run”– you will have result 1: “GI found”; 2) click the button “Renumber G2″ and “Run” — you will have result 2: “GI not found”; 3) copy G1 to G2 (button “G1->G2) and click the button “Run”– you will have result 3: “GI not found”. So, the program is unable to repeat its own result 1. And also, we may suppose that any counterexample for the algorithm is possible, but not for every random renumbering (result 2). And anyhow, even if my algorithm is not correct, this does not falsify my statements about journals: they did not find similar counterexample to reject my paper, but they used only their unproved belief that such algorithm is impossible.

        Thank you very much for your message, in the nearest future I will inspect the program to fix the bug. Perhaps, more precision is necessary to test such big graph. Have you an image (picture) of this graph? This image would be very helpful to analyze the graph.

        Best wishes!

      • Francesco Cri permalink
        May 30, 2010 5:35 pm

        I think that it is not a software bug. What I mean is this: place that graph in G1 field, then copy G1 to G2 using button “G1->G2” and only now click the button “Renumber G2″. (Is obvious that G1 is isomorphic to G2 ) the result is “GI not found” . So we have that for two isomorphic graphs G1 and G2, your software, that implements your polinomial time algorithm for GI, returns in output “NO” when the correct answer is “YES”.
        The same result remains for shell version usig G1 and G2 built as upon.
        So we have not a software bug related to a repetition of its own ‘correct’ result.
        I don’t understand what you mean for “And also, we may suppose that any counterexample for the algorithm is possible, but not for every random renumbering (result 2)”. Initially I’ve found this counterexample permutating the nodes of a graph using my own software and using the shell version of your software, when I’ve seen the button “Renumber G2” in the GUI version, then I’ve used it. So I think that the counterexample is a ‘correct counterexample’.

        It is a simple graph of 43 nodes, the image of G1 is here:

        Best wishes

  9. Michael Trofimov permalink
    May 31, 2010 3:42 am

    The fact is that after your graph the program memory seems to be corrupted, because Result 3 and Result 1 have to be the same. So, there is software bug definitely and it should be fixed first of all. Only after this correction of the program we can answer: is this graph counterexample for the algorithm? and why? I will report it here when this work will be done. Thank you for image of the graph.

    If we remove W-matrices comparison from procedure 1, then the graph from Fig.5 of the paper would be counterexample, but only when the program maps vertex 1 to vertex 14, which mapping is not observed for every random renumbering. As a rule, all possible renumbers are not worst cases for the program, but only some of them. Again, I will test your graph carefully. If we will find that your graph is real counterexample for the algorithm we will try to improve the algorithm: there is a lot of possibilities for that in frameworks of suggested approach.

    • Francesco Cri permalink
      June 3, 2010 3:03 pm

      Since you are convinced that the error is due to software bug then consider this 2 graphs:
      G1
      1-35, 1-36, 1-37, 2-35, 2-38, 2-41, 3-35, 3-39, 3-43, 4-35, 4-40, 4-42, 5-38, 5-39, 5-40, 6-36, 6-39, 6-42, 7-36, 7-40, 7-41, 8-36, 8-38, 8-43, 9-41, 9-42, 9-43, 10-37, 10-40, 10-43, 11-37, 11-38, 11-42, 12-37, 12-39, 12-41, 13-23, 13-24, 13-25, 13-26, 14-23, 14-28, 14-29, 14-30, 15-23, 15-32, 15-33, 15-34, 16-24, 16-27, 16-30, 16-33, 17-25, 17-27, 17-28, 17-34, 18-26, 18-27, 18-29, 18-32, 19-24, 19-29, 19-31, 19-34, 20-26, 20-28, 20-31, 20-33, 21-25, 21-30, 21-31, 21-32, 22-23, 22-24, 22-25, 22-26, 22-27, 22-28, 22-29, 22-30, 22-31, 22-32, 22-33, 22-34, 22-35, 22-36, 22-37, 22-38, 22-39, 22-40, 22-41, 22-42, 22-43

      G2
      1-35, 1-36, 1-37, 2-35, 2-38, 2-41, 3-35, 3-39, 3-23, 4-35, 4-40, 4-42, 5-38, 5-39, 5-40, 6-36, 6-39, 6-42, 7-36, 7-40, 7-41, 8-36, 8-38, 8-23, 9-41, 9-42, 9-23, 10-37, 10-40, 10-23, 11-37, 11-38, 11-42, 12-37, 12-39, 12-41, 13-43, 13-24, 13-25, 13-26, 14-43, 14-28, 14-29, 14-30, 15-43, 15-32, 15-33, 15-34, 16-24, 16-27, 16-30, 16-33, 17-25, 17-27, 17-28, 17-34, 18-26, 18-27, 18-29, 18-32, 19-24, 19-29, 19-31, 19-34, 20-26, 20-28, 20-31, 20-33, 21-25, 21-30, 21-31, 21-32, 22-43, 22-24, 22-25, 22-26, 22-27, 22-28, 22-29, 22-30, 22-31, 22-32, 22-33, 22-34, 22-35, 22-36, 22-37, 22-38, 22-39, 22-40, 22-41, 22-42, 22-23

      Where G2 is obtained from G1 exchanging the node number 43 to 23 and viceversa.
      Well, your algorithm returns in output “GI not found” that is not the correct answer.
      No correct result to repeat. No memory corruption. No use of your button “Renumber G2”. So there is no software bug definitely.

      Best wishes

  10. Michael Trofimov permalink
    June 4, 2010 2:56 am

    > Well, your algorithm returns in output
    Not my algorithm, but my program!
    >No memory corruption
    Why do you think so?
    Please, be patient – I’ll test it under debugger.
    With best wishes!

  11. June 13, 2010 4:28 am

    Bugs had been fixed, the program was updated (see new version 1.1.6). Thanks again for useful example. Now the program recognizes it correctly for different renumbers.

    • Francesco Cri permalink
      June 13, 2010 5:07 pm

      So now I’ve to suppose that your software implements your algorithm correctly, right? So if I found a counterexample for your software then this corresponds to a counterexample that disprove your algorithm definitely. Are you agree with this fact now?!

  12. June 14, 2010 5:21 am

    You asked philosophical question from Philosophy of computer science area. Did you see any non-trivial program, which is absolutely bag free?😉 To support a program you will need testers; program developer can not be a tester of the same program. It is common rule of software industry. But I have not software development firm and I am forced to support the program alone. Anyhow, if you will find another graph, which would not be recognized by the program, then please send me it (via this web-site or directly via email). And I’ll try to answer “what is wrong?” Ok?

    • Francesco Cri permalink
      June 14, 2010 9:49 am

      Sorry but this is not the right way to prove a so important conclusion. What I asked you is just a rhetorical question i.e. is a question for which anybody working in research area know the answer: if somebody states “hey I’ve an algorithm that solve the graph isomorphism problem in polynomial time!” adding also “the initial algortihm had been tested on test set included 95.000.000 graphs” (highlighting the use of a software) then in order to disprove what you claim is sufficient a counterexample. Your explanations about any counterexample seems to be “hey is not my fault, the algortihm is right but the software is not totally bug free”. This motivation starts to be inconsistent and is never used by researchers. Please consider also that the correctness of software is formally provable. So, how can you expect that some journal will public your paper? Assuming that some journal reviewer will found another counterexample, then he certainly will reject your publication without considering any of your stated motivations.
      Anyway, yes I found another graph for which I’ve merely permutated the nodes number by hand and for which your software returns “GI not found”.

      Best wishes

  13. June 14, 2010 5:26 am

    typo: bug free

  14. June 14, 2010 2:08 pm

    Sorry but

    1) a program itself proves nothing;
    2) a program is not algorithm;
    3) there are math proofs in my paper.

    Also you wrote:

    > this is not the right way to prove a so important conclusion.

    Sorry but here you did a big methodological mistake. Imre Lakatos described similar way in his well-known book “Proofs and Refutations” (1976, Cambridge: Cambridge University Press. ISBN 0-521-29038-4 & ISBN 978-0521290388). Also he noted that not every error is fatal error. So, if some journal reviewer found counterexample for MATH proof (marked “math”!), then he has formal right to reject this my paper. But from my side, I also have a right to improve my algorithm (into used frameworks) and resend revised paper again for new consideration. This is general way for scientific progress for “so important conclusion[s]”. So, you are welcome to send your new “counterexample”. For example, for your recent graph I fixed input error in the program: the problem was linked with LF, CR characters. Thanks but this is not counterexample for the algorithm, obviously. (You can analyze the source code to see it.)

    Again and again. I only state that the approach is valid to solve GI in poly time. Some bugs in software and in algorithm may be fixed in the result of discussion.

    And also: you did not answer my question “Did you see any non-trivial program, which is absolutely bug free?” – it was not rhetorical question!😉 How many versions of nauty were updated? My respect to Brendan McKay for this wonderful program!

    GI is extremely hard task – what’s why nobody solved it during last 30 years. And I do not think that today I have final solution, but I believe that I see a way to do it with your help.

    Thanks again.

  15. Francesco Cri permalink
    June 16, 2010 8:20 am

    Probably now I understand why it seems that you don’t understood of what I’m talking about.
    Your first 3 statements are:

    1) a program itself proves nothing;
    2) a program is not algorithm;
    3) there are math proofs in my paper.

    Have you studied computer science? if yes, are you joking?!
    Briefly:
    1)A program is itself a specification of an effective method
    2)Have you ever heard the Church-Turing thesis?
    “Any computer program in any of the conventional programming languages can be translated into a Turing machine, and any Turing machine can be translated into most programming languages, so the thesis is equivalent to saying that the conventional programming languages are sufficient to express any algorithm and v.v..”. So any program is an algorithm, also an “Hello world” program is an algorithm since it can be executed by a TM.
    3)There are no math proof of the correcteness of your program in your paper
    Search with google “Program Correctness coppit” and click on “quick view” of the first link that you’ll obtain.

    “Testing can show the presence of errors, but not their absence.” E. W. Dijkstra. What I’m talking about in my last reply was just this!! i.e. you have to prove the correctness of your program in order to prove that there is no errors in it. Once you have done this, then every counterexample for your program is also a counterexample for your algorithm. (As program you can consider the shell version that is more simple to manage than the gui version).

    About my graph, remember that I found it by hand i.e. permutating the nodes number by hand, so there was no CR or LF characters related to the output error. Moreover I’ve noted that also click on the button “Renumber G2” that error appears. But initially my counterexample was found just using intuition and my skills related to GI😉

    Since you need an answer about the question “Did you see any non-trivial program, which is absolutely bug free?”, yes I’ve seen a lot of them, i.e. every “correct” implementation of the Dijkstra algorithm.

    You write “I do not think that today I have final solution” (for GI problem) so, please explain me why you keep on arxiv a paper named “Polynomial Time Algorithm for Graph Isomorphism Testing”?
    I like to contribute to this research area, but, as you probably understood, I’m one of those that believe that GI is not in P.

    Best wishes

  16. Michael Trofimov permalink
    June 16, 2010 10:10 am

    I’m 30 years in computer sci area. So I ignore you aggressive questions “Have you ever heard the Church-Turing thesis?” etc. Please, see more info about me in Intel site, for example http://software.intel.com/en-us/articles/blackbelt-hall-of-fame/ Top Community Masterminds section.

    About my question: “Did you see any non-trivial program, which is absolutely bug free?” – now I ask you again: Did you see any non-trivial compiler, which is absolutely bug free?😉 When I said “program” I meant real exe-file, not abstract product for abstract machine! You wrote:

    > About my graph, remember that I found it by hand i.e. permutating the nodes number by hand, so there was no CR or LF characters related to the output error

    Look at TextEdit component documentation: it inserts CR&LF just after you did “Paste”. When you inspect real program behavior you have to assume features of environment (CPU, OS & libraries etc.), which features may be very specific and not documented. So nobody from real programmers can be agreed with your infantile ultimatum request of absolutely bug free. But this is computer sci. philosophy only (theory vs. practice), if you really found any bug, please, report it.

  17. Francesco Cri permalink
    June 17, 2010 1:46 pm

    Sorry but my question was not aggressive but just hilarious provocative; what someone write in internet is often misunderstood since nobody can hear/see the expression used.
    I had already seen your page in another discussion here: http://news.ycombinator.com/item?id=1263493 so I knew about the mastermind section nevertheless I written you my “aggressive” question😀

    In order to prevet any “bug-free or not bug-free” issue, please consider only the shell version of your program (so we avoid the problem related to the TextEdit component, ok?!).

    Open notepad, place in it the following graph:
    1-27, 1-28, 1-29, 1-30, 1-31, 1-32, 1-33, 1-34, 1-35, 1-36, 1-37, 1-38, 1-39, 1-40, 1-41, 1-42, 1-43, 1-44, 1-45, 1-46, 1-47, 2-28, 2-29, 2-30, 2-31, 2-32, 2-33, 2-34, 2-35, 2-36, 2-37, 2-38, 2-39, 2-40, 2-41, 2-42, 2-43, 2-44, 2-45, 2-46, 2-47, 2-48, 3-25, 3-29, 3-30, 3-31, 3-32, 3-33, 3-34, 3-35, 3-36, 3-37, 3-38, 3-39, 3-40, 3-41, 3-42, 3-43, 3-44, 3-45, 3-46, 3-47, 3-48, 4-25, 4-26, 4-30, 4-31, 4-32, 4-33, 4-34, 4-35, 4-36, 4-37, 4-38, 4-39, 4-40, 4-41, 4-42, 4-43, 4-44, 4-45, 4-46, 4-47, 4-48, 5-25, 5-26, 5-27, 5-31, 5-32, 5-33, 5-34, 5-35, 5-36, 5-37, 5-38, 5-39, 5-40, 5-41, 5-42, 5-43, 5-44, 5-45, 5-46, 5-47, 5-48, 6-25, 6-26, 6-27, 6-28, 6-32, 6-33, 6-34, 6-35, 6-36, 6-37, 6-38, 6-39, 6-40, 6-41, 6-42, 6-43, 6-44, 6-45, 6-46, 6-47, 6-48, 7-25, 7-26, 7-27, 7-28, 7-29, 7-33, 7-34, 7-35, 7-36, 7-37, 7-38, 7-39, 7-40, 7-41, 7-42, 7-43, 7-44, 7-45, 7-46, 7-47, 7-48, 8-25, 8-26, 8-27, 8-28, 8-29, 8-30, 8-34, 8-35, 8-36, 8-37, 8-38, 8-39, 8-40, 8-41, 8-42, 8-43, 8-44, 8-45, 8-46, 8-47, 8-48, 9-25, 9-26, 9-27, 9-28, 9-29, 9-30, 9-31, 9-35, 9-36, 9-37, 9-38, 9-39, 9-40, 9-41, 9-42, 9-43, 9-44, 9-45, 9-46, 9-47, 9-48, 10-25, 10-26, 10-27, 10-28, 10-29, 10-30, 10-31, 10-32, 10-36, 10-37, 10-38, 10-39, 10-40, 10-41, 10-42, 10-43, 10-44, 10-45, 10-46, 10-47, 11-25, 11-26, 11-27, 11-28, 11-29, 11-30, 11-31, 11-32, 11-33, 11-37, 11-38, 11-39, 11-40, 11-41, 11-42, 11-43, 11-44, 11-45, 11-46, 11-47, 11-48, 12-25, 12-26, 12-27, 12-28, 12-29, 12-30, 12-31, 12-32, 12-33, 12-34, 12-38, 12-39, 12-40, 12-41, 12-42, 12-43, 12-44, 12-45, 12-46, 12-47, 12-48, 13-25, 13-26, 13-27, 13-28, 13-29, 13-30, 13-31, 13-32, 13-33, 13-34, 13-35, 13-39, 13-40, 13-41, 13-42, 13-43, 13-44, 13-45, 13-46, 13-47, 13-48, 14-25, 14-26, 14-27, 14-28, 14-29, 14-30, 14-31, 14-32, 14-33, 14-34, 14-35, 14-36, 14-40, 14-41, 14-42, 14-43, 14-44, 14-45, 14-46, 14-47, 14-48, 15-25, 15-26, 15-27, 15-28, 15-29, 15-30, 15-31, 15-32, 15-33, 15-34, 15-35, 15-36, 15-37, 15-41, 15-42, 15-43, 15-44, 15-45, 15-46, 15-47, 15-48, 16-25, 16-26, 16-27, 16-28, 16-29, 16-30, 16-31, 16-32, 16-33, 16-34, 16-35, 16-36, 16-37, 16-38, 16-42, 16-43, 16-44, 16-45, 16-46, 16-47, 16-48, 17-25, 17-26, 17-27, 17-28, 17-29, 17-30, 17-31, 17-32, 17-33, 17-34, 17-35, 17-36, 17-37, 17-38, 17-39, 17-43, 17-44, 17-45, 17-46, 17-47, 17-48, 18-25, 18-26, 18-27, 18-28, 18-29, 18-30, 18-31, 18-32, 18-33, 18-34, 18-35, 18-36, 18-37, 18-38, 18-39, 18-40, 18-44, 18-45, 18-46, 18-47, 18-48, 19-25, 19-26, 19-27, 19-28, 19-29, 19-30, 19-31, 19-32, 19-33, 19-34, 19-35, 19-36, 19-37, 19-38, 19-39, 19-40, 19-41, 19-45, 19-46, 19-47, 19-48, 20-25, 20-26, 20-27, 20-28, 20-29, 20-30, 20-31, 20-32, 20-33, 20-34, 20-35, 20-36, 20-37, 20-38, 20-39, 20-40, 20-41, 20-42, 20-46, 20-47, 20-48, 21-25, 21-26, 21-27, 21-28, 21-29, 21-30, 21-31, 21-32, 21-33, 21-34, 21-35, 21-36, 21-37, 21-38, 21-39, 21-40, 21-41, 21-42, 21-43, 21-47, 21-48, 22-25, 22-26, 22-27, 22-28, 22-29, 22-30, 22-31, 22-32, 22-33, 22-34, 22-35, 22-36, 22-37, 22-38, 22-39, 22-40, 22-41, 22-42, 22-43, 22-44, 22-48, 23-25, 23-26, 23-27, 23-28, 23-29, 23-30, 23-31, 23-32, 23-33, 23-34, 23-35, 23-36, 23-37, 23-38, 23-39, 23-40, 23-41, 23-42, 23-43, 23-44, 23-45, 24-26, 24-27, 24-28, 24-29, 24-30, 24-31, 24-32, 24-33, 24-34, 24-35, 24-36, 24-37, 24-38, 24-39, 24-40, 24-41, 24-42, 24-43, 24-44, 24-45, 24-46

    save it in a file named G1.txt
    Open a new file in notepad and copy G1 in it, then apply the following permutations nodes:
    1 13, 10 48, 28 6, 224, 20 46, 11 12, 3 45, 15 47, 744, 831, 936, 14 39, 1644, 1743.
    Obtaining the following graph:
    13-27, 13-6, 13-29, 13-30, 13-8, 13-32, 13-33, 13-34, 13-35, 13-9, 13-37, 13-38, 13-14, 13-40, 13-41, 13-42, 13-17, 13-7, 13-3, 13-20, 13-15, 24-6, 24-29, 24-30, 24-8, 24-32, 24-33, 24-34, 24-35, 24-9, 24-37, 24-38, 24-14, 24-40, 24-41, 24-42, 24-17, 24-7, 24-3, 24-20, 24-15, 24-10, 45-25, 45-29, 45-30, 45-8, 45-32, 45-33, 45-34, 45-35, 45-9, 45-37, 45-38, 45-14, 45-40, 45-41, 45-42, 45-17, 45-7, 45-3, 45-20, 45-15, 45-10, 4-25, 4-26, 4-30, 4-8, 4-32, 4-33, 4-34, 4-35, 4-9, 4-37, 4-38, 4-14, 4-40, 4-41, 4-42, 4-17, 4-7, 4-3, 4-20, 4-15, 4-10, 5-25, 5-26, 5-27, 5-8, 5-32, 5-33, 5-34, 5-35, 5-9, 5-37, 5-38, 5-14, 5-40, 5-41, 5-42, 5-17, 5-7, 5-3, 5-20, 5-15, 5-10, 28-25, 28-26, 28-27, 28-6, 28-32, 28-33, 28-34, 28-35, 28-9, 28-37, 28-38, 28-14, 28-40, 28-41, 28-42, 28-17, 28-7, 28-3, 28-20, 28-15, 28-10, 16-25, 16-26, 16-27, 16-6, 16-29, 16-33, 16-34, 16-35, 16-9, 16-37, 16-38, 16-14, 16-40, 16-41, 16-42, 16-17, 16-7, 16-3, 16-20, 16-15, 16-10, 31-25, 31-26, 31-27, 31-6, 31-29, 31-30, 31-34, 31-35, 31-9, 31-37, 31-38, 31-14, 31-40, 31-41, 31-42, 31-17, 31-7, 31-3, 31-20, 31-15, 31-10, 36-25, 36-26, 36-27, 36-6, 36-29, 36-30, 36-8, 36-35, 36-9, 36-37, 36-38, 36-14, 36-40, 36-41, 36-42, 36-17, 36-7, 36-3, 36-20, 36-15, 36-10, 48-25, 48-26, 48-27, 48-6, 48-29, 48-30, 48-8, 48-32, 48-9, 48-37, 48-38, 48-14, 48-40, 48-41, 48-42, 48-17, 48-7, 48-3, 48-20, 48-15, 12-25, 12-26, 12-27, 12-6, 12-29, 12-30, 12-8, 12-32, 12-33, 12-37, 12-38, 12-14, 12-40, 12-41, 12-42, 12-17, 12-7, 12-3, 12-20, 12-15, 12-10, 11-25, 11-26, 11-27, 11-6, 11-29, 11-30, 11-8, 11-32, 11-33, 11-34, 11-38, 11-14, 11-40, 11-41, 11-42, 11-17, 11-7, 11-3, 11-20, 11-15, 11-10, 1-25, 1-26, 1-27, 1-6, 1-29, 1-30, 1-8, 1-32, 1-33, 1-34, 1-35, 1-14, 1-40, 1-41, 1-42, 1-17, 1-7, 1-3, 1-20, 1-15, 1-10, 39-25, 39-26, 39-27, 39-6, 39-29, 39-30, 39-8, 39-32, 39-33, 39-34, 39-35, 39-9, 39-40, 39-41, 39-42, 39-17, 39-7, 39-3, 39-20, 39-15, 39-10, 47-25, 47-26, 47-27, 47-6, 47-29, 47-30, 47-8, 47-32, 47-33, 47-34, 47-35, 47-9, 47-37, 47-41, 47-42, 47-17, 47-7, 47-3, 47-20, 47-15, 47-10, 44-25, 44-26, 44-27, 44-6, 44-29, 44-30, 44-8, 44-32, 44-33, 44-34, 44-35, 44-9, 44-37, 44-38, 44-42, 44-17, 44-7, 44-3, 44-20, 44-15, 44-10, 43-25, 43-26, 43-27, 43-6, 43-29, 43-30, 43-8, 43-32, 43-33, 43-34, 43-35, 43-9, 43-37, 43-38, 43-14, 43-17, 43-7, 43-3, 43-20, 43-15, 43-10, 18-25, 18-26, 18-27, 18-6, 18-29, 18-30, 18-8, 18-32, 18-33, 18-34, 18-35, 18-9, 18-37, 18-38, 18-14, 18-40, 18-7, 18-3, 18-20, 18-15, 18-10, 19-25, 19-26, 19-27, 19-6, 19-29, 19-30, 19-8, 19-32, 19-33, 19-34, 19-35, 19-9, 19-37, 19-38, 19-14, 19-40, 19-41, 19-3, 19-20, 19-15, 19-10, 46-25, 46-26, 46-27, 46-6, 46-29, 46-30, 46-8, 46-32, 46-33, 46-34, 46-35, 46-9, 46-37, 46-38, 46-14, 46-40, 46-41, 46-42, 46-20, 46-15, 46-10, 21-25, 21-26, 21-27, 21-6, 21-29, 21-30, 21-8, 21-32, 21-33, 21-34, 21-35, 21-9, 21-37, 21-38, 21-14, 21-40, 21-41, 21-42, 21-17, 21-15, 21-10, 22-25, 22-26, 22-27, 22-6, 22-29, 22-30, 22-8, 22-32, 22-33, 22-34, 22-35, 22-9, 22-37, 22-38, 22-14, 22-40, 22-41, 22-42, 22-17, 22-7, 22-10, 23-25, 23-26, 23-27, 23-6, 23-29, 23-30, 23-8, 23-32, 23-33, 23-34, 23-35, 23-9, 23-37, 23-38, 23-14, 23-40, 23-41, 23-42, 23-17, 23-7, 23-3, 2-26, 2-27, 2-6, 2-29, 2-30, 2-8, 2-32, 2-33, 2-34, 2-35, 2-9, 2-37, 2-38, 2-14, 2-40, 2-41, 2-42, 2-17, 2-7, 2-3, 2-20

    and save it as G2.txt.
    Then from shell run any of the following commands:
    mt2gi_cons 1 g1.txt g2.txt
    mt2gi_cons 2 g1.txt g2.txt
    mt2gi_cons 3 g1.txt g2.txt

    the output will be the same:
    >> Number of vertices is 48
    >> Number of edges is 503
    >> GI test: started 17/06/2010 20.32.36
    >> GI not found
    >> GI test: finished 17/06/2010 20.32.37
    Time is 0,485000386834145 sec.
    DebugFlag=0
    >> End ——————————-

    I continue to insist that, if your program (from now consider only shell version), is a correct implementation of your algorithm, then this instance of graphs needs to be considered as a counterexample that refutes your algorithm.

    Best wishes Mastemind😉

  18. Francesco Cri permalink
    June 17, 2010 1:52 pm

    It seems that some character is removed by the blog software in the reply, these are the right permutations nodes to apply:
    1–13, 10–48, 28–6, 2–24, 20–46, 11–12, 3–45, 15–47, 7–44, 8–31, 9–36, 14–39, 16–44, 17–43.

  19. Ross Snider permalink
    June 17, 2010 2:12 pm

    Michael and Francesco, I think I can clear up some of the confusion. I’ll do this by addressing Michael and discussing what I believe Francesco was getting at:

    Like the seL4 kernel (http://ertos.nicta.com.au/research/l4.verified/) and the program of White et al that proved the 4-color conjecture, Francesco asks that you go about proving that your program is formally correct (represents your maths wholey and correctly). If you do this, any error found in the output of your program will reflect errors in your maths. Running your program and obtaining outputs says essentially nothing about your maths unless you show its formal correctness (equivalence to the algorithm presented in the paper). For example, this is why in the conclusion of your paper you could write “The initial algorithm [15] had been tested on test set included about 95,000,000
    graphs containing up to 120 vertices” – yet have counterexamples easily found by a human adept.

    In any case, because your program wasn’t proven formally correct, those 95,000,000 graphs you tested mean essentially squat. I believe this the quibble that Francesco has. We’d all like to see the problem closed. Before we believe it is closed, however, we ought be presented with compelling evidence.

    He isn’t saying that by finding errors in your program he’s disproven your maths. You agree with him here. He’s asking that, before any effort is invested into verifying your maths – that you invest effort in verifying the correctness of your program. That way, one might go about trying inputs to your program in an attempt to find a counter-example without much wasted time or effort. He would agree that if no counterexample can be found in the formally correct program then the maths have to be looked at very seriously. The quibble about TMs was one of miscommunication. Your program is an algorithm – it just hasn’t been proven to be the (presumed) polynomial time algorithm presented in your paper.

  20. June 18, 2010 11:59 am

    — to Ross Snider:

    > If you do this, any error found in the output of your program will reflect errors in your maths

    Yes, but I do not see any real way to do it. I do not understand how I can verify exe-file compiled by Delphi compiler and linked with Delphi libraries to get 100% verification?😉

    > “The initial algorithm [15] had been tested on test set included about 95,000,000 graphs containing up to 120 vertices” – yet have counterexamples easily found by a human adept.
    […]
    > In any case, because your program wasn’t proven formally correct, those 95,000,000 graphs you tested mean essentially squat.

    Please, be attentive! I said clearly: this was another (initial, recursive) algorithm and so another program (See ref. [15]). BTW that program works correctly for all examples from here.

    > He isn’t saying that by finding errors in your program he’s disproven your maths. You agree with him here.

    I agree with you that finding errors in my program is not disproven my maths, but Francesco Cri wrote opposite😦 He wrote:

    > if I found a counterexample for your software then this corresponds to a counterexample that disprove your algorithm definitely.

    I still disagree with such infantile ultimatum request. Above I wrote:

    > If we remove W-matrices comparison from procedure 1, then the graph from Fig.5 of the paper would be counterexample, but only when the program maps vertex 1 to vertex 14

    It would be self-evident counter example to disprove math: gi program is not necessary to see that vertices 1,14 are not similar, but they have equal weights. But I have no idea why the current algorithm unable to solve examples by Francesco Cri. If he can explain this also, then I’ll consider this explanation as math refutation.

    — to Francesco Cri:

    > Open notepad, place in it the following graph
    […]
    > save it in a file named G1.txt

    It is not necessary for current version: I fixed input bug, so you can use GUI for input.

    Thank you for bug report. I need some time to fix this bug (today I found that the bug is linked with non-correct calculation of W-matrix, perhaps I mixed array indices in the program). Unfortunately, your graph is too large, so step-by-step debugging will be very time expensive. Can you find smaller graph to reproduce this bug?

  21. Francesco Cri permalink
    June 18, 2010 1:13 pm

    Just a bit of clarifications:

    To Michael:
    In one of my first replies I written what you have ‘partial’ reported, namely:
    >So now I’ve to suppose that your software implements your algorithm correctly, right? So if I found >a counterexample for your software then this corresponds to a counterexample that disprove your >algorithm definitely

    In other words what I written is true under the assumption that your program correctly implements your algorithm. To be honest, my first assumption before any reply in this blog was that you had a formal proof of the correctness of your program i.e. your program reflects your math as well explained by Ross Snider.
    Please consider that my words are not “infantile ultimatum”, they are just a necessary logical consequence under the assumption that your program is correct in the sense of above.

    A formal proof of the correctness of your program is not based looking at the .exe file but translating your program in a logic formal language and then, using well-know inferences methods, proving its correctness (this in very informally words ). For a general explanation you can see these slides:
    http://www.cs.umd.edu/class/spring2005/cmsc838p/Slides/proofs.ppt

    Some years ago I was working on a deterministic-polynomial-time algorithm for GI and I’ve seen that the graphs that represents very hard instances for GI are those graphs with particular symmetries.
    Briefly what I’m saying is that every time that was found an invariance that characterizes a set of graphs then it seems that a new set of graphs with a new and different invariances can be build.
    If this conjecture were true then GI is not in P, but I’ve not a formal proof for it😦

    Sorry but I’ve not a smaller graph now to reproduce what you define a bug🙂 I’ve only many hard instances for GI problem that have more than 50 vertices. It would be a good idea if you increase the maximum vertices number to at least 100.

    Best wishes

  22. June 19, 2010 6:11 am

    Formal proof of program correctness is very old idea. For example, in 1980 Peter Grogono described similar methods in his textbook Programming in Pascal (Addison-Wesley, Inc.). I agree that these methods have a good future. But for 100% verification we need 100% verified CFU, 100% correct OS, compiler and libraries. Also we should exclude human factor from verification, i.e. we need automatic AI prover. However, perhaps you are right and even partial proof of this program correctness would be useful. See procedure ComputeW in UnitGITest.pas. There is a bug in this procedure. Can you find this bug via verification?

    > Briefly what I’m saying is that every time that was found an invariance that characterizes a set of graphs then it seems that a new set of graphs with a new and different invariances can be build. If this conjecture were true then GI is not in P, but I’ve not a formal proof for it

    My approach is not simple topological index (graph invariant) calculation. The simple classical method is 1) calculate index for the first graph; 2) calculate index for the second graph; 3) compare this index values; 4) stop. For example, this scheme was suggested for Hosoya index for tasks of computer (math) chemistry. Hosoya index is one integer number for a graph (total number of matchings in graph), i.e. it is global index. I use local index for every vertex – this is the first difference. I use real numbers (2nd diff.) and also I use their combinations into W-matrix (3rd diff.), but also I use iteration process to change the indices (4th diff.). The initial algorithm was recursive backtracking algorithm, so it is able to test correctly every graphs pair. When we had inspected the program for 95,000,000 graphs we saw that for worst cases the algorithm is much more faster than exp(n). I think your idea that GI is not in P based on your impressions of trivial usage of trivial invariants.

    > It would be a good idea if you increase the maximum vertices number to at least 100.

    Yes. The maximum vertices limit should be removed from the program (in the shell I used unlimited dynamic arrays). There is only one problem – size of W-matrix. To save memory I will need to use special methods for sparse matrices. It will be the next step after correction of current program. I think that in the case of unlimited program the limited program also would be necessary as example of the simplest realization of the algorithm.

    • Francesco Cri permalink
      June 19, 2010 8:16 am

      I use a different way to be sure that I’ve a correct program. Once that I’ve proved the correctness using formal language, then I implement it in at least 2 programming languague. My favorites are java and php. Why this way? Because so now I’ve two logical abstract CPUs that execute the same formally correct program and it begins to be unlikely that any problems related to libraries, compilers ect ect occurs.

      Your approach seems to be similar to this one: http://www.dharwadker.org/tevet/isomorphism.
      But today I’ve tested their program using the same graph of my last reply in this blog.
      Well, the output is:
      “Graph A and Graph B have the same sign frequency vectors in lexicographic order but cannot be isomorphic.”
      If you wan to to test their program you can use this file as graphA:
      http://www.wikiupload.com/gCrZRVPb
      and this file as graphB:
      http://www.wikiupload.com/RotaQjJh
      graphB.txt is just an adjacency matrix abtained from graphA.txt permutating columns and rows.
      So under the assumption that their program is a correct implementation of their algorithm, then they have not prooved that GI is in P.

      Best wishes

  23. June 20, 2010 7:25 am

    > I use a different way to be sure that I’ve a correct program.

    I.e. you think that the way you noted (http://www.cs.umd.edu/class/spring2005/cmsc838p/Slides/proofs.ppt) is not complete?😉

    > Once that I’ve proved the correctness using formal language, then I implement it in at least 2 programming languague. My favorites are java and php. Why this way?

    You can do the same error in 2 implementations.

    > Because so now I’ve two logical abstract CPUs that execute the same formally correct program and it begins to be unlikely that any problems related to libraries, compilers ect ect occurs.

    You have the same physical CPU, the same OS, the same API calls etc. But surely, if somebody will make independent realization of my algorithm, then I will be very thankful for such verification.

    > Your approach seems to be similar to this one

    No. I use vertex weight, i.e. solutions of system (1) (see my paper), they do not.

    > So under the assumption that their program is a correct implementation of their algorithm, then they have not prooved that GI is in P.

    I do not think that I should consider their approach via web-site. I do know this article, no comments more🙂

  24. June 20, 2010 10:39 am

    You might be interested in trying the program on the two pairs of graphs available here
    http://abel.math.umu.se/~klasm/Data/GraphIso/

    They are two pairs of graphs which are difficult to separate for certain graph invariants. The graphs are in the graph6 format.

  25. Francesco Cri permalink
    June 20, 2010 11:07 am

    Hum, I think that once we are sure that an algorithm is formally correct i.e. reflects its math conceptualisation and its math conceptualisation is reflected by the algorithm, then remains only to translate it into a programming language but this process is trivial. The possibility that exists errors due to OS, CPU, compiler or libraries is very remote but not impossible. So using different libraries and different compilers we can reduce to 0% that possibility. Consider that php and java are also portables i.e. we can test the algorithm on different real CPUs. So doing we have not the same CPU, not the same OS and not the same API calls😉

    • June 21, 2010 4:43 am

      > translate it into a programming language but this process is trivial

      It is not trivial. Proof. If the process is trivial, then trivial translator program is possible to do such process automatically. This translator has an algorithm description from a paper in input, and a programming language source code in output…

      Also, everybody is able to write 2*2=5. And everybody is able to write it twice😦

      > So doing we have not the same CPU, not the same OS and not the same API calls

      Yes, in theory. But in practice today we usually use Intel-compatible CPUs, MS Windows and Linux OSs etc. Today there is no non-trivial code, which code had been done from scratch. A bug like virus may migrate from system to system. Perhaps, only Oberon system on real (non virtual) Oberon computer may be free of such bugs (but it may has similar bugs, done by Wirth when he realized the system from scratch). However, I have not physical Oberon computer🙂

  26. June 22, 2010 6:09 am

    Francesco Cri: > the following graph:
    1-27, 1-28, 1-29, 1-30, 1-31, 1-32, 1-33, 1-34, 1-35, 1-36, 1-37, 1-38, 1-39, 1-40, 1-41, 1-42, 1-43, 1-44, 1-45, 1-46, 1-47, 2-28, 2-29, 2-30, 2-31, 2-32,

    Ok now, I found simplification of the algorithm and its proof, also you wrote:

    > It would be a good idea if you increase the maximum vertices number to at least 100.

    Done. The maximum vertices number is 120. Please, see beta-version
    http://mt2.comtv.ru/MT2GI-1.1.7.zip
    The simplification is not documented yet, so there is exe-file only.

  27. Francesco Cri permalink
    June 22, 2010 7:24 am

    It has not changed so much. Consider this 54 vertices graph:

    1-30, 1-31, 1-32, 1-33, 1-34, 1-35, 1-36, 1-37, 1-38, 1-39, 1-40, 1-41, 1-42, 1-43, 1-44, 1-45, 1-46, 1-47, 1-48, 1-49, 1-50, 1-51, 1-52, 1-53, 2-31, 2-32, 2-33, 2-34, 2-35, 2-36, 2-37, 2-38, 2-39, 2-40, 2-41, 2-42, 2-43, 2-44, 2-45, 2-46, 2-47, 2-48, 2-49, 2-50, 2-51, 2-52, 2-53, 2-54, 3-28, 3-32, 3-33, 3-34, 3-35, 3-36, 3-37, 3-38, 3-39, 3-40, 3-41, 3-42, 3-43, 3-44, 3-45, 3-46, 3-47, 3-48, 3-49, 3-50, 3-51, 3-52, 3-53, 3-54, 4-28, 4-29, 4-33, 4-34, 4-35, 4-36, 4-37, 4-38, 4-39, 4-40, 4-41, 4-42, 4-43, 4-44, 4-45, 4-46, 4-47, 4-48, 4-49, 4-50, 4-51, 4-52, 4-53, 4-54, 5-28, 5-29, 5-30, 5-34, 5-35, 5-36, 5-37, 5-38, 5-39, 5-40, 5-41, 5-42, 5-43, 5-44, 5-45, 5-46, 5-47, 5-48, 5-49, 5-50, 5-51, 5-52, 5-53, 5-54, 6-28, 6-29, 6-30, 6-31, 6-35, 6-36, 6-37, 6-38, 6-39, 6-40, 6-41, 6-42, 6-43, 6-44, 6-45, 6-46, 6-47, 6-48, 6-49, 6-50, 6-51, 6-52, 6-53, 6-54, 7-28, 7-29, 7-30, 7-31, 7-32, 7-36, 7-37, 7-38, 7-39, 7-40, 7-41, 7-42, 7-43, 7-44, 7-45, 7-46, 7-47, 7-48, 7-49, 7-50, 7-51, 7-52, 7-53, 7-54, 8-28, 8-29, 8-30, 8-31, 8-32, 8-33, 8-37, 8-38, 8-39, 8-40, 8-41, 8-42, 8-43, 8-44, 8-45, 8-46, 8-47, 8-48, 8-49, 8-50, 8-51, 8-52, 8-53, 8-54, 9-28, 9-29, 9-30, 9-31, 9-32, 9-33, 9-34, 9-38, 9-39, 9-40, 9-41, 9-42, 9-43, 9-44, 9-45, 9-46, 9-47, 9-48, 9-49, 9-50, 9-51, 9-52, 9-53, 9-54, 10-28, 10-29, 10-30, 10-31, 10-32, 10-33, 10-34, 10-35, 10-39, 10-40, 10-41, 10-42, 10-43, 10-44, 10-45, 10-46, 10-47, 10-48, 10-49, 10-50, 10-51, 10-52, 10-53, 11-28, 11-29, 11-30, 11-31, 11-32, 11-33, 11-34, 11-35, 11-36, 11-40, 11-41, 11-42, 11-43, 11-44, 11-45, 11-46, 11-47, 11-48, 11-49, 11-50, 11-51, 11-52, 11-53, 11-54, 12-28, 12-29, 12-30, 12-31, 12-32, 12-33, 12-34, 12-35, 12-36, 12-37, 12-41, 12-42, 12-43, 12-44, 12-45, 12-46, 12-47, 12-48, 12-49, 12-50, 12-51, 12-52, 12-53, 12-54, 13-28, 13-29, 13-30, 13-31, 13-32, 13-33, 13-34, 13-35, 13-36, 13-37, 13-38, 13-42, 13-43, 13-44, 13-45, 13-46, 13-47, 13-48, 13-49, 13-50, 13-51, 13-52, 13-53, 13-54, 14-28, 14-29, 14-30, 14-31, 14-32, 14-33, 14-34, 14-35, 14-36, 14-37, 14-38, 14-39, 14-43, 14-44, 14-45, 14-46, 14-47, 14-48, 14-49, 14-50, 14-51, 14-52, 14-53, 14-54, 15-28, 15-29, 15-30, 15-31, 15-32, 15-33, 15-34, 15-35, 15-36, 15-37, 15-38, 15-39, 15-40, 15-44, 15-45, 15-46, 15-47, 15-48, 15-49, 15-50, 15-51, 15-52, 15-53, 15-54, 16-28, 16-29, 16-30, 16-31, 16-32, 16-33, 16-34, 16-35, 16-36, 16-37, 16-38, 16-39, 16-40, 16-41, 16-45, 16-46, 16-47, 16-48, 16-49, 16-50, 16-51, 16-52, 16-53, 16-54, 17-28, 17-29, 17-30, 17-31, 17-32, 17-33, 17-34, 17-35, 17-36, 17-37, 17-38, 17-39, 17-40, 17-41, 17-42, 17-46, 17-47, 17-48, 17-49, 17-50, 17-51, 17-52, 17-53, 17-54, 18-28, 18-29, 18-30, 18-31, 18-32, 18-33, 18-34, 18-35, 18-36, 18-37, 18-38, 18-39, 18-40, 18-41, 18-42, 18-43, 18-47, 18-48, 18-49, 18-50, 18-51, 18-52, 18-53, 18-54, 19-28, 19-29, 19-30, 19-31, 19-32, 19-33, 19-34, 19-35, 19-36, 19-37, 19-38, 19-39, 19-40, 19-41, 19-42, 19-43, 19-44, 19-48, 19-49, 19-50, 19-51, 19-52, 19-53, 19-54, 20-28, 20-29, 20-30, 20-31, 20-32, 20-33, 20-34, 20-35, 20-36, 20-37, 20-38, 20-39, 20-40, 20-41, 20-42, 20-43, 20-44, 20-45, 20-49, 20-50, 20-51, 20-52, 20-53, 20-54, 21-28, 21-29, 21-30, 21-31, 21-32, 21-33, 21-34, 21-35, 21-36, 21-37, 21-38, 21-39, 21-40, 21-41, 21-42, 21-43, 21-44, 21-45, 21-46, 21-50, 21-51, 21-52, 21-53, 21-54, 22-28, 22-29, 22-30, 22-31, 22-32, 22-33, 22-34, 22-35, 22-36, 22-37, 22-38, 22-39, 22-40, 22-41, 22-42, 22-43, 22-44, 22-45, 22-46, 22-47, 22-51, 22-52, 22-53, 22-54, 23-28, 23-29, 23-30, 23-31, 23-32, 23-33, 23-34, 23-35, 23-36, 23-37, 23-38, 23-39, 23-40, 23-41, 23-42, 23-43, 23-44, 23-45, 23-46, 23-47, 23-48, 23-52, 23-53, 23-54, 24-28, 24-29, 24-30, 24-31, 24-32, 24-33, 24-34, 24-35, 24-36, 24-37, 24-38, 24-39, 24-40, 24-41, 24-42, 24-43, 24-44, 24-45, 24-46, 24-47, 24-48, 24-49, 24-53, 24-54, 25-28, 25-29, 25-30, 25-31, 25-32, 25-33, 25-34, 25-35, 25-36, 25-37, 25-38, 25-39, 25-40, 25-41, 25-42, 25-43, 25-44, 25-45, 25-46, 25-47, 25-48, 25-49, 25-50, 25-54, 26-28, 26-29, 26-30, 26-31, 26-32, 26-33, 26-34, 26-35, 26-36, 26-37, 26-38, 26-39, 26-40, 26-41, 26-42, 26-43, 26-44, 26-45, 26-46, 26-47, 26-48, 26-49, 26-50, 26-51, 27-29, 27-30, 27-31, 27-32, 27-33, 27-34, 27-35, 27-36, 27-37, 27-38, 27-39, 27-40, 27-41, 27-42, 27-43, 27-44, 27-45, 27-46, 27-47, 27-48, 27-49, 27-50, 27-51, 27-52.

    Place it in G1 folder, copy to G2, and repeat the following 2 steps until the renumbering is right to get in output “GI not found”:
    1)Click on “Renumber G2”
    2)Click on “Run” and see the result.

    • June 23, 2010 11:03 am

      Today I found this software bug, the problem is linked with floating point calculations in real computer. I am thinking about. Thank you.

    • June 26, 2010 4:35 am

      Noted precision problem is not problem of my algorithm only, but it is common general problem – see the book by R. Hammer a.o. (ref [5] in my paper) for more details. In introduction of this book they noted well-known article by Nickel (1982) “Can we trust the results of our computing?” Under debugger I saw that the algorithm works correctly, but classical Gauss method may get different rounding errors for floating point calculations and so on (the same problems noted in Hammer’s book). I used programming trick to get the same errors of accuracy of calculations and now the new version 1.2.0 is able to recognize all graphs you noted here. However, the program still uses usual trivial approach for floating point calculations, which may be not sufficient for some sophisticated graphs. It seems, that in my paper I did a mistake, when I estimated necessary accuracy via star-like graphs (Appendix 3). Perhaps, for practical usage the program may use self-validating numerics (reliable computations) and Pascal-XSC, but for current moment I do not want to develop practical GI method, before theoretical proof is not approved. Thanks again for your examples, but they reflect implementation problems only.

      Download current version from http://mt2.comtv.ru/MT2GI-1.2.0.zip
      I decreased the maximum vertices number, it is 60.

  28. September 23, 2010 2:35 am

    The paper was updated: http://arxiv.org/abs/1004.1808
    The program was updated.

  29. Francesco Cri permalink
    October 2, 2010 2:53 am

    Hi Michael,

    sorry to reply you so late, thanks al tot for the acknowledgment in you paper but my full name is Francesco Cristiano (i cut my surname just for semplicity). Well, some days ago I’ve tested your new program and it seems that there is still something wrong. This is an example related to what I mean:
    Graph 1:
    1-32, 1-33, 1-34, 1-35, 1-36, 1-37, 1-38, 1-39, 1-40, 1-41, 1-42, 1-43, 1-44, 1-45, 1-46, 1-47, 1-48, 1-49, 1-50, 1-51, 1-52, 1-53, 1-54, 1-55, 1-56, 1-57, 1-58, 1-59, 2-31, 2-34, 2-35, 2-36, 2-37, 2-38, 2-39, 2-40, 2-41, 2-42, 2-43, 2-44, 2-45, 2-46, 2-47, 2-48, 2-49, 2-50, 2-51, 2-52, 2-53, 2-54, 2-55, 2-56, 2-57, 2-58, 2-59, 2-60, 3-31, 3-32, 3-35, 3-36, 3-37, 3-38, 3-39, 3-40, 3-41, 3-42, 3-43, 3-44, 3-45, 3-46, 3-47, 3-48, 3-49, 3-50, 3-51, 3-52, 3-53, 3-54, 3-55, 3-56, 3-57, 3-58, 3-59, 3-60, 4-31, 4-32, 4-33, 4-36, 4-37, 4-38, 4-39, 4-40, 4-41, 4-42, 4-43, 4-44, 4-45, 4-46, 4-47, 4-48, 4-49, 4-50, 4-51, 4-52, 4-53, 4-54, 4-55, 4-56, 4-57, 4-58, 4-59, 4-60, 5-31, 5-32, 5-33, 5-34, 5-37, 5-38, 5-39, 5-40, 5-41, 5-42, 5-43, 5-44, 5-45, 5-46, 5-47, 5-48, 5-49, 5-50, 5-51, 5-52, 5-53, 5-54, 5-55, 5-56, 5-57, 5-58, 5-59, 5-60, 6-31, 6-32, 6-33, 6-34, 6-35, 6-38, 6-39, 6-40, 6-41, 6-42, 6-43, 6-44, 6-45, 6-46, 6-47, 6-48, 6-49, 6-50, 6-51, 6-52, 6-53, 6-54, 6-55, 6-56, 6-57, 6-58, 6-59, 6-60, 7-31, 7-32, 7-33, 7-34, 7-35, 7-36, 7-39, 7-40, 7-41, 7-42, 7-43, 7-44, 7-45, 7-46, 7-47, 7-48, 7-49, 7-50, 7-51, 7-52, 7-53, 7-54, 7-55, 7-56, 7-57, 7-58, 7-59, 7-60, 8-31, 8-32, 8-33, 8-34, 8-35, 8-36, 8-37, 8-40, 8-41, 8-42, 8-43, 8-44, 8-45, 8-46, 8-47, 8-48, 8-49, 8-50, 8-51, 8-52, 8-53, 8-54, 8-55, 8-56, 8-57, 8-58, 8-59, 8-60, 9-31, 9-32, 9-33, 9-34, 9-35, 9-36, 9-37, 9-38, 9-41, 9-42, 9-43, 9-44, 9-45, 9-46, 9-47, 9-48, 9-49, 9-50, 9-51, 9-52, 9-53, 9-54, 9-55, 9-56, 9-57, 9-58, 9-59, 9-60, 10-31, 10-32, 10-33, 10-34, 10-35, 10-36, 10-37, 10-38, 10-39, 10-42, 10-43, 10-44, 10-45, 10-46, 10-47, 10-48, 10-49, 10-50, 10-51, 10-52, 10-53, 10-54, 10-55, 10-56, 10-57, 10-58, 10-59, 10-60, 11-31, 11-32, 11-33, 11-34, 11-35, 11-36, 11-37, 11-38, 11-39, 11-40, 11-43, 11-44, 11-45, 11-46, 11-47, 11-48, 11-49, 11-50, 11-51, 11-52, 11-53, 11-54, 11-55, 11-56, 11-57, 11-58, 11-59, 11-60, 12-31, 12-32, 12-33, 12-34, 12-35, 12-36, 12-37, 12-38, 12-39, 12-40, 12-41, 12-44, 12-45, 12-46, 12-47, 12-48, 12-49, 12-50, 12-51, 12-52, 12-53, 12-54, 12-55, 12-56, 12-57, 12-58, 12-59, 12-60, 13-31, 13-32, 13-33, 13-34, 13-35, 13-36, 13-37, 13-38, 13-39, 13-40, 13-41, 13-42, 13-45, 13-46, 13-47, 13-48, 13-49, 13-50, 13-51, 13-52, 13-53, 13-54, 13-55, 13-56, 13-57, 13-58, 13-59, 13-60, 14-31, 14-32, 14-33, 14-34, 14-35, 14-36, 14-37, 14-38, 14-39, 14-40, 14-41, 14-42, 14-43, 14-46, 14-47, 14-48, 14-49, 14-50, 14-51, 14-52, 14-53, 14-54, 14-55, 14-56, 14-57, 14-58, 14-59, 14-60, 15-31, 15-32, 15-33, 15-34, 15-35, 15-36, 15-37, 15-38, 15-39, 15-40, 15-41, 15-42, 15-43, 15-44, 15-47, 15-48, 15-49, 15-50, 15-51, 15-52, 15-53, 15-54, 15-55, 15-56, 15-57, 15-58, 15-59, 15-60, 16-31, 16-32, 16-33, 16-34, 16-35, 16-36, 16-37, 16-38, 16-39, 16-40, 16-41, 16-42, 16-43, 16-44, 16-45, 16-48, 16-49, 16-50, 16-51, 16-52, 16-53, 16-54, 16-55, 16-56, 16-57, 16-58, 16-59, 16-60, 17-31, 17-32, 17-33, 17-34, 17-35, 17-36, 17-37, 17-38, 17-39, 17-40, 17-41, 17-42, 17-43, 17-44, 17-45, 17-46, 17-49, 17-50, 17-51, 17-52, 17-53, 17-54, 17-55, 17-56, 17-57, 17-58, 17-59, 17-60, 18-31, 18-32, 18-33, 18-34, 18-35, 18-36, 18-37, 18-38, 18-39, 18-40, 18-41, 18-42, 18-43, 18-44, 18-45, 18-46, 18-47, 18-50, 18-51, 18-52, 18-53, 18-54, 18-55, 18-56, 18-57, 18-58, 18-59, 18-60, 19-31, 19-32, 19-33, 19-34, 19-35, 19-36, 19-37, 19-38, 19-39, 19-40, 19-41, 19-42, 19-43, 19-44, 19-45, 19-46, 19-47, 19-48, 19-51, 19-52, 19-53, 19-54, 19-55, 19-56, 19-57, 19-58, 19-59, 19-60, 20-31, 20-32, 20-33, 20-34, 20-35, 20-36, 20-37, 20-38, 20-39, 20-40, 20-41, 20-42, 20-43, 20-44, 20-45, 20-46, 20-47, 20-48, 20-49, 20-52, 20-53, 20-54, 20-55, 20-56, 20-57, 20-58, 20-59, 20-60, 21-31, 21-32, 21-33, 21-34, 21-35, 21-36, 21-37, 21-38, 21-39, 21-40, 21-41, 21-42, 21-43, 21-44, 21-45, 21-46, 21-47, 21-48, 21-49, 21-50, 21-53, 21-54, 21-55, 21-56, 21-57, 21-58, 21-59, 21-60, 22-31, 22-32, 22-33, 22-34, 22-35, 22-36, 22-37, 22-38, 22-39, 22-40, 22-41, 22-42, 22-43, 22-44, 22-45, 22-46, 22-47, 22-48, 22-49, 22-50, 22-51, 22-54, 22-55, 22-56, 22-57, 22-58, 22-59, 22-60, 23-31, 23-32, 23-33, 23-34, 23-35, 23-36, 23-37, 23-38, 23-39, 23-40, 23-41, 23-42, 23-43, 23-44, 23-45, 23-46, 23-47, 23-48, 23-49, 23-50, 23-51, 23-52, 23-55, 23-56, 23-57, 23-58, 23-59, 23-60, 24-31, 24-32, 24-33, 24-34, 24-35, 24-36, 24-37, 24-38, 24-39, 24-40, 24-41, 24-42, 24-43, 24-44, 24-45, 24-46, 24-47, 24-48, 24-49, 24-50, 24-51, 24-52, 24-53, 24-56, 24-57, 24-58, 24-59, 24-60, 25-31, 25-32, 25-33, 25-34, 25-35, 25-36, 25-37, 25-38, 25-39, 25-40, 25-41, 25-42, 25-43, 25-44, 25-45, 25-46, 25-47, 25-48, 25-49, 25-50, 25-51, 25-52, 25-53, 25-54, 25-57, 25-58, 25-59, 25-60, 26-31, 26-32, 26-33, 26-34, 26-35, 26-36, 26-37, 26-38, 26-39, 26-40, 26-41, 26-42, 26-43, 26-44, 26-45, 26-46, 26-47, 26-48, 26-49, 26-50, 26-51, 26-52, 26-53, 26-54, 26-55, 26-58, 26-59, 26-60, 27-31, 27-32, 27-33, 27-34, 27-35, 27-36, 27-37, 27-38, 27-39, 27-40, 27-41, 27-42, 27-43, 27-44, 27-45, 27-46, 27-47, 27-48, 27-49, 27-50, 27-51, 27-52, 27-53, 27-54, 27-55, 27-56, 27-59, 27-60, 28-31, 28-32, 28-33, 28-34, 28-35, 28-36, 28-37, 28-38, 28-39, 28-40, 28-41, 28-42, 28-43, 28-44, 28-45, 28-46, 28-47, 28-48, 28-49, 28-50, 28-51, 28-52, 28-53, 28-54, 28-55, 28-56, 28-57, 28-60, 29-31, 29-32, 29-33, 29-34, 29-35, 29-36, 29-37, 29-38, 29-39, 29-40, 29-41, 29-42, 29-43, 29-44, 29-45, 29-46, 29-47, 29-48, 29-49, 29-50, 29-51, 29-52, 29-53, 29-54, 29-55, 29-56, 29-57, 29-58, 30-32, 30-33, 30-34, 30-35, 30-36, 30-37, 30-38, 30-39, 30-40, 30-41, 30-42, 30-43, 30-44, 30-45, 30-46, 30-47, 30-48, 30-49, 30-50, 30-51, 30-52, 30-53, 30-54, 30-55, 30-56, 30-57, 30-58, 30-59

    Then: 1)copy to G2, 2)renumber G2, 3) run.

    After a lot of minutes (around 8 mins for my laptop) you will get “GI not found” such as the following output:
    http://img29.imageshack.us/f/mt2gierror.jpg/

    Maybe you have some issue with the approximation of real numbers? You should know that there exists software tools that can help us to represents any real number with any approximation i.e. the java class BigDecimal and BigInteger.

    Best Wishes

  30. October 2, 2010 4:42 am

    Hi Francesco,

    Thank you for the new bug report. Yes, unfortunately, the program is still something wrong😦 You found memory overflow error, the program terminated its calculations and exited via exception. Yes, I found a lot of tools for real numbers approximation etc. Perhaps, I’ll use some of these tools for next version. Also it would be very good idea if somebody will port my program to java. (Unfortunately, I have no experience in java programming.) Also I will correct your full name in next version of the paper (sorry for this mistake). This time I am waiting for bug reports about theoretical proof of the algorithm.

    Best Wishes

    • October 13, 2010 5:03 am

      Francesco,

      Addition. I got the same picture as your (http://img29.imageshack.us/f/mt2gierror.jpg/) on my PC. But I pressed “Ok” and got following picture:

      where error messages are marked.
      Cited from Delphi-7 Help:
      “ERangeError occurs in Delphi code when range checking is enabled and an ordinal values goes outside its declared range.”
      I added a line from UnitBigIntLib source to the screen shot:
      “BigIntSize=60; // size of TBigInt array”.
      Ok.

      Best Wishes

  31. Francesco Cri permalink
    October 17, 2010 1:58 pm

    Michael,

    why you don’t increase BigIntSize=120? Or better give user the option to change that value run-time? i.e. using a configuration file for your program that will be read every time that it starts?

    Thanks
    Regards

    • October 18, 2010 4:48 am

      Francesco,
      It would be too slow. Again: the goal of current version of the program is demonstration of details of possible implementation. This is addition to the algorithm description. And it provides completeness of the description, not more. For this goal, the simplest implementation is necessary. To compare big graphs you need fast implementation with parallel multiplication etc. For such optimization the program has to be rewritten – this would be very long work. Also a supercomputer would be very useful for testing. If and when I will find a grant, I will do this work😉
      Best Wishes

  32. Kyle Jones permalink
    October 19, 2010 11:20 am

    The last bit of discussion shows the importance of a solid test set. Anyone know where a good collection of test graphs for this problem can be found? amalfi.dis.unina.it is supposed to have a large collection of graphs, but I’ve tried for days to connect to the site with no success.

    • rjlipton permalink*
      October 19, 2010 9:31 pm

      A good class of graphs are the strongly regular ones.

  33. October 24, 2010 5:01 am

    A month ago I updated the paper “Polynomial Time Algorithm for Graph Isomorphism Testing” http://arxiv.org/abs/1004.1808 . Nobody found any error in my proof.

    • Ross Snider permalink
      April 11, 2011 1:11 pm

      Michael –

      When you say this you should be clear about the number of field experts who have looked at your proof and concurred with its correctness (rather than emphasizing the lack of disagreement). One could, for example, very easily write something in a personal journal, untouched by every human eye – then proceed to make the claim that nobody has dis-proven the statement contained within your journal. I think you would agree that this would not suffice as evidence for the correctness, soundness, or truthiness of such a statement. It is important in this case not to highlight the lack of conversation but instead the plethora of it. It would be nice of you to include a list of mathematicians who you have convinced your algorithm works and respected publication venues which are showcasing and popularizing your ideas.

      Evidence is gathered through a long process involving multiple domain experts. While your paper is available to the web through arXiv, this does not mean it is receiving this all too important sort of dialog. I would suggest, if you are confident in your results, that you submit your paper to journals and make all of the tweaks suggested by reviewers. It is typically looked down on to make small revisions to your paper every time an error is found. It is advisable that you only submit your paper when you are very confident it is close to its final form.

      Finally, remember that since you are asserting a controversial statement it is your job to provide solid evidence for your claim – not the other way around. You ought to provide intellectual stepping stones to other people to facilitate a clean conversation about your work. Your work should be organized and use familiar notation. When drastically new techniques are used, you should highlight these with examples and exposition. Other good advice can be found around the web.

      On a side note, concerning your earlier statement that “I said clearly: this was another (initial, recursive) algorithm and so another program (See ref. [15]). BTW that program works correctly for all examples from here.”, you may consider publishing this program you believe correctly implements your (presumed) polynomial time algorithm – since it is clear you believe it implements your algorithm correctly and it is clear you believe the one you have released and discussed with others here is flawed.

      • April 12, 2011 6:37 am

        Ross –
        Thank you for your message. Recently the paper had been rejected again from well-known computer sci. journal. Unfortunately the first reviewer seems to have misinterpreted my paper: some of the flaws that he finds are consequences of this misinterpretation. (In fact he retold my paper and he substituted its structure.) He does not take note of Assertion 1 and its conclusions, and writes: “Even if you assign different B values to vertices, I do not see how this ensures that the mapping choice taken at each vertex of G is always the correct or unique one”. However, my Conclusion 2 from Assertion 1 ensures this. In my paper, Lemma 2 is correct, but in his interpretation Lemma 2 seems to be incorrect. (The conclusion is that if the graphs are isomorphic and the solutions of system of linear equations are obtained by mutual permutation and have all different coordinates, then the corresponding permutation of the coordinates of the vectors gives isomorphism of the graphs). At the same time, the reviewer did provide the very interesting comment that my proof of Proposition 1, page 5 is redundant. However, a few lines of formulas (which he found useless) surely does not warrant rejection of the paper. Also, I am in agreement with the reviewer’s note about implementation, and in fact I wrote in the paper: “The algorithm had been implemented into a program (see Implementation section, 6), this implementation may be very helpful for better understanding of suggested approach”. The implementation was done to show that the description of the algorithm is sufficient to implement it. The second reviewer found a bug in the program, but it does not follow from this that: “The algorithm does not work. The invariant used is not complete. Hence, the paper should be rejected”. It would be correct to say: “The current implementation is not free of bugs”. It does not mean that the algorithm does not work. As the first reviewer noted: “the objective of this work seems rather theoretical than practical”. I asked my colleagues about this journal decision. One of them (well-known computer sci. professor of well-known university) wrote: “The comments do not seem to be consistent with the recommendation ‘definitely reject’. After reading the comments, I would expect ‘minor revisions’.” At the same time nobody wants to agree with my proof in public. Morris Kline noted such behavior in his book “Mathematics. The Loss of Certainty”: he wrote that today mathematicians are afraid to do an error, they solve only tasks, which may be solved easily, to keep their reputation.

  34. September 17, 2011 1:25 pm

    I found that graph isomorphism problem may be reduced to particular case of common representatives system finding: http://arxiv.org/abs/1004.1808

    • June 19, 2013 7:46 am

      I revised the approach cardinally: “The essence of this work is a method of reduction of general task of graph isomorphism testing to more particular task of labeled trees isomorphism, that task was solved earlier.” (http://arxiv.org/abs/1004.1808)

Trackbacks

  1. Giving Some Thanks Around the Globe « Gödel’s Lost Letter and P=NP

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s