Jump to content

Talk:Graph isomorphism/Archive 1

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
Archive 1

?

http://arxiv.org/abs/math/0607770 —Preceding unsigned comment added by 212.22.96.208 (talk) 12:24, 30 January 2008 (UTC)

Known Algorithms

Nauty, VF2, and others are discussed in this paper http://amalfi.dis.unina.it/graph/db/papers/benchmark.pdf

Here is an algorithm that I've been using to solve the ISOMORPHISM problem in the general case of non-directed graphs.

Okay... here's my algorithm for determining graph isomorphims.

Let G1 and G2 be graphs. G1 has m,n vertices and edges; G2 has x,y vertices and edges.

First, does m =x ? If yes = they are potentially isomorphims (as they have the same number of vertices) Next, does n = y ? If yes = they are potentially isomorphims (as they have the same number of edges)

Next, compute eatch vertex degree in G1, and G2. (that is, count how many edges are associated with each vertex).

For G1, sort the vetrex degrees in decending order - we'll call this S1 For G2, sort the vertex degrees in decending order - we'll call this S2

If S1 = S2, they could be isomorphic as they are equal in the sense that the vertex weights are the same.

Loop:

Now from G1 remove all vertices with the weight of (m-1). Now from G2 remove all vertices with the weight of (m-1). Now the number of edges and the sorted vertex weights may be different! Update the edge count of all vertices

For G1, sort the vetrex degrees in decending order - we'll call this S3 For G2, sort the vertex degrees in decending order - we'll call this S4 If S3 = S4 they could be isomorphic as they are equal in the sense that the vertex weights are the same. Count the number of edges in G1 and G2; if equal, we're still portentially isomorphic

Go back to Loop: and repeat with (m-2), (m-3) until it is 0.

Copyright August 2007, Andrew Walduck. Permission granted to Wikiversity to licences under the GFDL.

andrew.walduck@gmail.com

74.99.31.225 04:54, 7 September 2007 (UTC)

<NOTES>* I tried to prove this: for I = 0 - trival case for I = 1 - trival case assume its true for I = N, then prove N+1. Consider the graph X1 with n, Y1 with n nodes also - they're isomorphisms Add node P to graph X1, and Q to Y1 (the N+1 part) ( If P == Q then the sorted node weight graphs will be the same, if p != Q then the sorted node weight graphs will be different. 48NQTF5

Retrieved from "http://en.wikiversity.org/wiki/School_of_Mathematics:Introduction_to_Graph_Theory:Problems_1"

This is a standard approach but it runs into difficulties with regular graphs. You can try to compute more powerful information at each vertex than just its degree that might help better to distinguish them from each other, say the vector of distances to all other vertices, but you will still run into trouble with distance-regular graphs. —David Eppstein 05:26, 7 September 2007 (UTC)

Hi David... could you provide an example of both 2 regular graphs that are isomorphims? Also, distance regular graphs??? Thanks Andrew Walduck 74.99.31.225 17:54, 11 September 2007 (UTC)

It's not quite the same as distance-regular, but Brendan McKay has encoded adjacency matrices of many strongly regular graphs at http://cs.anu.edu.au/~bdm/data/graphs.html —Preceding unsigned comment added by David Eppstein (talk • contribs) 18:13, 11 September 2007 (UTC)

Hi David... I tried to come up with a regular matrix and its isomorphism. I came up with 2 triangles, basicially a 6 node graph that has all vertices with the same edge count of 2. I tried to come up with an isomorphism but failed... :-( However, if you have two graphs, both 2-regular with 6 nodes each, the algorithm still works, you remove the 6 nodes with 2 vertices... note that my algorithm does not give the mapping array, it will only tell you "yes or no"... Cheers Andrew Walduck 74.99.31.225 20:34, 11 September 2007 (UTC)

If you could come up with a 3 regular graph

2-regular graphs are just cycles and disjoint unions of cycles, not interesting from a graph isomorphism point of view. The page I pointed you at has large numbers of 3-regular graphs, but if you want two specific nonisomorphic ones with the same numbers of vertices, try Desargues graph and dodecahedron. Of course, one of these graphs is bipartite and the other isn't, so they're not difficult to tell apart, but it doesn't sound like your algorithm will determine that. —David Eppstein 20:38, 11 September 2007 (UTC)

Hi David, I looked at the Desargues graph and the dodecahedron they clearly break my algorithm! both have vertices = 20, edges = 30, and edges per vertex of 3... so they disappear on the first pass if you remove all vertices with edge count of 3 at the same time!! Back to the drawing board... maybe we should just delete this mess??? Andrew Walduck 74.99.31.225 21:10, 11 September 2007 (UTC) Hi David... I walked through the algorithm on the Desargues graph and the dodecahedron. If you only remove 1 node with the maximum number of edges each time, it "works for a while" and then the sorted node-edge-count arrays (the S1, S2 etc) eventually become different... If you look at my "proof" its clear that it (my algorithm) doesn't work for "regular graphs" - you can't just add one node to each and maintain regularity... Its interesting that the smallest and largest cycle size is different for these two graphs... for Desargues graph its 6 and for the dodecahedron its 5... this is probably another condition that should be checked for isomorphism...(thanks for the counter example!) Can you find a "regular graph" with the same cycle sizes (in addition to node count, and edge count) that is not isomorphic?

cheers Andrew Walduck 74.99.31.225 21:45, 11 September 2007 (UTC)

Andrew, before inventing bicycles, please take a look into several quite old but still quite informative surveys of the graph isomorphism problem. About 20-30 years ago it was a fashionable topic, dubbed "Graph Isomorphism Disease". There were literally hundreds of articles og GI-problem published, with numerous algorithms. It seems that new generations have thoroughly forgotten the "prior art". I am adding references to surveys into the article.
What is more, wikipedia talk pages are for discussion article content. It is not a message board for doing research in math. Please feel free to communicate with David via private channels and don't clutter this page, which is workspace for wikipedia editors working on the article. `'Míkka 22:20, 11 September 2007 (UTC)


IMHO

following new important result may be added to the article:

An effective algorithm for graph isomorphim testing was used for organic chemistry tasks, the algorithm complexity does not depend directly on the number of vertices of given graphs. Authors tested this algorithm for ~95,000,000 graphs, and did not find any limitation to use this approach for other types of graphs.

M.I.Trofimov, E.A.Smolenskii, Russian Chemical Bulletin, 2005, Vol. 54, 9, 2235. (http://dx.doi.org/10.1007/s11172-006-0105-6).

Tim32 16:15, 7 October 2007 (UTC)

I'm not convinced that this is a sufficiently notable contribution to the problem to include in the article. I note for instance that Google scholar doesn't find any citations. It is not new or surprising that graph isomorphism may be solved efficiently on many practical instances. Assuming it's the one entitled "application of electronegativity indices...", it's even less surprising that nontrivial vertex labelings can help a lot in speeding up the task. —David Eppstein 04:08, 22 October 2007 (UTC)

Dear Prof Eppstein,

The fact is that this algorithm complexity does not depend directly on the number of vertices of given graphs. Perhaps, you know another similar facts? Yes, "It is not new or surprising that graph isomorphism may be solved efficiently" for example by Nauty. The Nauty program is very effective realization of very effective algorithm, but the algorithm is O(exp(n)) complete, where n is the number of vertices of given graphs.

Yes, I also very like Google, but very often Google is unable to find any info for me. So, IMHO, that Google scholar doesn't find any citations is Google problem ;-) And also, are you sure that citations counting is the best method to get scientific truth?

Also, I am surprised that I wrote about this my idea to edit this page a long time ago. You did not send this your comment before this editing work was done, but just after the moment when the page was updated. It looks like indelicate act against my work for Wiki.

BTW, did you read this article?

--Tim32 08:37, 22 October 2007 (UTC)

Since you insist on being responded to: In fact, I have not read the article. My reading your article and making a judgement here about its worthiness would be perilously close to WP:OR, precisely because I do know something about the subject. At Wikipedia, we should not be in the business of sieving through uncited recent research papers attempting to pick out the diamonds among so much dross — there is no particular hurry, we can wait until the research attracts the attention it deserves, and then judge its notability by the quality of that attention. That goes not just for whether or not to create an article on a subject, but also for whether to include new results in an article. Graph isomorphism is such a big subject that one can't simply cite everything relevant (as I might do for some topics with smaller literatures) so we need to use good encyclopedic principles to choose what's important, and that means having the patience to let the dust settle in the scientific literature first. —David Eppstein 06:48, 25 October 2007 (UTC)

1) This my addition was not an original research, because there was the source printed in scientific journal by well-known publisher (Springer). "Primary sources that have been published by a reliable source may be used in Wikipedia, but only with care, because it is easy to misuse them. " (WP:OR#Primary, secondary, and tertiary sources) I used this source with care.

2) You wrote: "we can wait until the research attracts the attention" - No! very often we can not wait! Otherwise, we lost the general Wiki advantage: please see, Wikipedia:About#Wikipedia vs. paper encyclopedias. Otherwise, we replace the neutral point of view with conservative point of view.

3) Also, you wrote: "Graph isomorphism is such a big subject that one can't simply cite everything relevant" Yes, agreed in common sense. But disagreed for this case. It is not "everything relevant", but very-very important. NP-complexity is the most important point for Graph isomorphism problem. If you know another facts pro- or contra- you have to add them to the article. The current edition looks like very poor informed in contrast with paper encyclopedias. However, you want to wait, you do not want to improve the article, and moreover you block other user to edit it. And moreover you do not want to discuss it: before my edition I asked about here and I heard nothing from you. Sorry, but may I remember you that this article is not your personal article.

4) May I note, also, that you tell me a lot about Wiki rules, but say nothing about the subject. ("In fact, I have not read the article.") However we have "WP:Ignore all rules" rule ;-) "Rules have zero importance compared to that goal." (Wikipedia:What "Ignore all rules" means) So, let you read this article to explain here why it is not so important, or let you restore my edition, before somebody else will get any valid argument against. This article was printed two years ago, and during this time period nobody reports about any error in it.

In a few words: I noted very important fact ("...complexity does not depend directly on the number of vertices of given graphs") that has been published by a reliable source. I asked you "Do you know another similar facts?" -- You did not answer this my question.

--Tim32 10:09, 25 October 2007 (UTC)

I didn't read the entire article, but searched it for some relevant terms. I couldn't find the authors' claim that the algorithm complexity is not directly dependent on the number of vertices. They do state "(...) the number of iterations also depend [sic] only slightly on the number of vertices (...)" (pages 2241 and 2244, emphasis mine); they do not clarify what they mean by this 'slight' dependence.
Were you maybe confused by their statement that "(...) the result is independent of enumeration of vertices." (page 2242, emphasis mine)? As far as I can tell, they mean the order in which the vertices are processed, not their number.
Finally, I note that the authors only considered graphs with up to 12 vertices in their tests.
Regards, Phaunt 12:00, 4 November 2007 (UTC)

"The recursion depth and the number of iterations in algorithm 3 depend on the number and size of partition blocks for the sets of the solutions of the systems of linear equations for the vertex weights obtained by consecutive replacement of the initial weights by the modified ones […], being only slightly dependent on the number of vertices m, just like the number of identical solutions of the system of linear equations of the type (2) is not simply related to the number, m, of the unknown quantities. The number and sizes of the partition blocks depend on the initial weights and degrees of vertices and on the discriminating capability of the index employed for the weights. They also depend, in a complex fashion, on the symmetry of the system of equations. In turn, this symmetry is directly related to the symmetry of the adjacency matrix of the corresponding graph. Each replacement of the initial weight of a vertex by the modified weight leads to a strong lowering of the symmetry of the system of equations, thus dividing the partition into progressively decreasing blocks and minimizing the enumeration." (p.2244).

Also you wrote: "I note that the authors only considered graphs with up to 12 vertices in their tests" it is not right. "The test set for the method proposed included a total of 95,000,000 molecules containing up to sixty carbon atoms." (p.2235, abstracts)

"Sixty carbon atoms" mean graphs up to 120 vertices.

--Regards, Tim32 17:27, 5 November 2007 (UTC)

I still don't see what this "slight" dependency means. AFAIK, they don't give a general mathematical relation between the number of vertices and number of iterations.
As to the number of vertices, the number of 95,000,000 in the abstract seems to refer to the summed value of K in Table 1 (p.2239). You can see that this table considers graphs of up to 12 vertices only.
In addition, as David Eppstein said, it is well known that the GI problem can be solved relatively easily in many cases; this is already in the article. In my opinion, the paper you refer to doesn't make any further sweeping statements that should be incorporated.
Regards, Phaunt 10:53, 7 November 2007 (UTC)

One thing missing in the above discussion is that the paper is NOT, in fact, a reliable source. It is a practical solution to a problem in applied chemistry, written by chemists, reviewed by their chemist peers, and published by a chemical journal. Such a publication is a perfectly acceptable source for issues in chemistry, but certainly not for issues in theoretical computer science. -- EJ 11:58, 7 November 2007 (UTC)

To:Phaunt, Re: there are Tables 2,3,4 (p.2171) in the next page also:"The total number of generated graphs G was 93,160,816 (Table 1) + 560,000 (Table 2) + 1,112,718(Table 3) + 200,000 (Table 4) = 95,033,534." (p.2241) "K is the number of external calls of the IsoTest procedure (Algorithm 3);" (p. 2239)
Also, do you know that the number of identical solutions of the system of linear equations is not related to the number of the unknown quantities? (If not, please, read any textbook of linear algebra before.) And anyhow please, read the Algorithm 3 description. Sorry, but it is too hard to explain something from the text, which text you did not read.
To: EJ,Re: Very strange reason. (But, firstly, a bit correction: this is not applied chemistry, this is fundamental (theoretical) chemistry.) It seems you want to say that "theoretical computer science" is absolutely isolated from other scientific areas and so any achievement in any area has no influence on the computer sci. However, there are a lot of opposite well-known examples in history of science. Quantum physics and quantum chemistry, for instance. Didn't you think that 2*2 is 4 for theoretical computer science, but is 5 for chemistry? ;-) Or may be you think, that well-known scientific journal printed by well-known publisher has no specialist in graph theory area? BTW, articles by Smolenskii were noted in well-known book: Alexander A. Zykov, Fundamentals of Graph Theory, Moscow, Idaho, USA: BCS Assotiates, 1990. --Tim32 13:48, 7 November 2007 (UTC)

Colleagues, you are wasting your time on a totally moot issue simply because you didn't take a boring step to actually look into the article or at least its summary. The author clearly writes: "The test set for the method proposed included a total of 95,000,000 molecules containing up to sixty carbon atoms." 60 for the number of vertices is a ridiculously small number to talk about in terms of computational complexity. A possible talk could be the efficiency of implementation, but the author gives no comparison with other approaches. There are no mentions of third-party, independent evaluations of the algorithm. There are hundreds of GI algorithms published, and each author says theirs is the best. Wikipedia is not a place for peer review of numerous math articles. I suggest to no longer waste time on this discussion unless sources are provided of other experts publish the discussion of this algorithm. `'Míkka 17:15, 7 November 2007 (UTC)

Wow! You used absolute weapon for any discussion - Paradox of the heap : you wrote: "60 for the number of vertices is a ridiculously small number to talk about in terms of computational complexity". It is universal method against every investigation: "authors used too small test set". And it has no sense what is exact size of this test set: 10 members, 100 members, 1K or 1 M members sizes may be classified as "too small". But unfortunately for this your "argument" this test set is for illustration only in the article, because the Algorithm 3 is not heuristic algorithm. For example, well-known Euclidean algorithm does not need any test set to see its correctness, because it is not heuristic algorithm as well.
Also you wrote: "A possible talk could be the efficiency of implementation, but the author gives no comparison with other approaches." – Other approaches are O(exp(n)) complete, where n is the number of vertices of given graphs. This one does not depend on n. Any comparison more?
You wrote: "There are hundreds of GI algorithms published, and each author says theirs is the best." Yes, but it is not argument at all. Moreover, I noted this algorithm not because it is the best of all, but only because this one does not depend on n. Do you see the difference?
And also you wrote: "Colleagues, you are wasting your time…" IMHO, the colleagues wasting MY time, because they did not read the article (you noted this fact also:), and so, one of the colleagues, mixed the total number of generated graphs and the number of external calls etc.
BTW, you wrote "the author…", but note, please, the article signed by two authors. --Tim32 08:47, 8 November 2007 (UTC)
First off, take it easy and remain civil, please.
The number of 95,000,000 test cases you wanted to add to the article is hardly relevant: the great majority of these (not all of them, I submit) is for graphs with up to 12 vertices as you surely also see.
Most importantly, the authors nowhere write that the complexity does not depend on the number of vertices. They say that the number of iterations is "not simply related" to the number of vertices (which just means they cannot express an upper bound in terms of the number of vertices, not that it doesn't exist); however, clearly the matrix operations depend on the number of vertices. The authors themselves write at the very end of the paper that "to this day, it remains unclear whether GI is NP-complete or not". If they had found an algorithm with time complexity unrelated (or even polynomially related) to the number of vertices, surely they would have noted that.
Again, the authors note that their approach works well on a number of specific cases, but this is already in the wikipedia article.
Finally, if you feel this is a waste of your time, nobody is forcing you to pursue this debate. I don't think I myself will continue it for much longer. Phaunt 11:01, 8 November 2007 (UTC)

Yes, of course, please, remain civil!

And I think, for any civil discussion of any text, is necessary to read this text before…:) Othervise totalitar style of discussion will win. For example, and only for example!, I do remember totalitar style of some discussions, which discussions took place many years ago in the Soviet Union, when everybody had began his/her speech from the words: "I did not read this novel by Solzhenitsyn [or Boris Pasternak ], but I want to say…" The similar discussion took place in chemical area and so on… Sorry for this reminiscence…

The most important point (thank you for this interesting question): you wrote: "however, clearly the matrix operations depend on the number of vertices". Yes! Ok! But there is no contradiction. The Gauss algorithm was used, its complexity is O(n3). For simplified understanding I can try to write down following expressions (I do understand that some criticism may be possible for these expressions; note, please, following is only for simplification): for this case the function k(f+n3) may be estimated as O(ku), where n is the number of graph vertices; f,u are some functions…; k is the number of Gauss calls; k,f,u does not depend on n. For example, something similar W. Lipski reproduced in his book Kombinatoryka dla Programistow, [Combinatorics for Programmers], Wydawnictwa Naukowo-Techniczne, Warzawa, 1982, for Hopcroft–Karp algorithm (maximum matchings): estimation O((m+n) n1/2) he replaced with O(n5/2), where m is number of edges; n is number of vertices.

About "95,000,000 test cases": there are 93,160,816 test cases for graphs with up to 12 vertices, and ~2 M for other cases (up to 120). I think, that inspite of 93 M >> 2M, this 2 M set is hardly relevant as well. However, it is an example (an illustration only) – please, see my reply to 'Míkka.

Also you wrote: "The authors themselves write at the very end of the paper that "to this day, it remains unclear whether GI is NP-complete or not". If they had found an algorithm with time complexity unrelated (or even polynomially related) to the number of vertices, surely they would have noted that." -- It is very interesting for me to read about myself: what we wanted to say... Please, be attentive and compare my email from Wiki user page with email from the article -- you will see this is the same email address, which begins from mtrofimov@… Yes, my name is Michael Trofimov and I am the author (one from two) of this article. (I thought, you had found this fact yourself.) First of all, we wrote also:

"In spite of the fact that this result is surely expected, its explanation in terms of formal estimates of computational complexity faces problems. Criticism has been repeatedly expressed in the graph theory studies, concerning practical limitations of the method of estimates of the hard-to-solve problems and the notion of NP-completeness (see., e.g., Ref. 28). [...] therefore, we will only mention that real performance has as much in common with the theoretical complexity as ideal gas with real gas or as famous MIX ideal computer by Knuth with Pentium 4."(p.2245)

Yes, today I do not know "whether GI is NP-complete or not", moreover I am not sure that NP concept is valid for GI;)

Anyhow, I am sure that this discussion is very important for Wiki. (I used Wiki a few years, but only a month ago I became registered user.) As I wrote to Prof Eppstein:

"You wrote: "we can wait until the research attracts the attention" - No! very often we can not wait! Otherwise, we lost the general Wiki advantage: please see, Wikipedia:About#Wikipedia vs. paper encyclopedias. Otherwise, we replace the neutral point of view with conservative point of view."

And finally, yes "nobody is forcing you[me] to pursue this debate". Yes, that investigation was finished, and this time I have another work and another problems to solve. I only want to add a little more info to this Wiki article. I believe it may be useful for somebody who finds in Internet more info that he/she is able to read in paper encyclopedias. (Also, as I wrote already, this discussion is becoming very important for "the general Wiki advantage".) I do not think that I waste of my time for productive work for Wiki. And to make our work productive: ladies and gentelmen, please, read any text attentively before discuss it. --Tim32 17:56, 10 November 2007 (UTC)

No, I will not read the entire article. I spent enough time on this issue as it is; I'm sorry. However, I do believe I have seen enough of the article (in particular, I already read all the phrases you cite above) to be able to make the following statements, which are partially a reiteration from above:
  1. First you assert ("this one does not depend on n", above) that the algorithm's complexity is constant with regard to the number of vertices, which I dismissed by pointing out the graph operations, and now you write that the polynomial complexity of the matrix operations (a clear dependency) does not matter. That is a drastic change of view, but probably you just miswrote. But still, you did not adress my point that the authors do not express an upper bound on the amount of necessary iterations in the number of vertices, nor do they claim that there is no relation at all (i.e. that the amount of iterations is constant in the number of vertices).
  2. I mentioned the amount of 95,000,000 because your edit included this figure. I am glad to see that you now agree that this is not relevant.
  3. The authors demonstrated an approach that they claim works well for some cases; they included some experiments to support this claim. However, this does not render their approach interesting enough to include in the article; the article already mentions that efficient algorithms exist for specific instances. If and when the authors are able to clearly define a specific set of instances and express a theoretical polynomial upper bound on the time complexity of their algorithm for these instances, this might warrant inclusion.
  4. Finally, as others already wrote and regardless of any of the previous points I made, it still holds that the medium of publication is not a reliable source for graph theory. If the authors' claim is truly valid, they are able to formally prove it, and it is indeed a nontrivial new result, it would probably be easy to get it published in a reliable resource on graph theory. At that point, it can certainly be incorporated into Wikipedia. It wouldn't have mattered if I completely agreed with your claim or not; verifiability is of prime importance.
I am sorry to have to criticise the result you published. I continued writing in the third person because we are debating a published result, not a wikipedian's opinion (which would be inappropriate). Please be aware of possible conflicts of interest, however nice it would be to have your publication cited here. I hope you can see reason in my points. It seems that there is little hope for including your findings at this point; you could try to bring attention to this debate via WP:RFC, but I'm afraid it won't help.
With this, I think I'll stop contributing to this discussion. Best regards, Phaunt 00:52, 12 November 2007 (UTC)

The fact is that today the majority of mathematics considers GI problem as NP complete, at the same time nobody can prove it. It looks like a myth. In this situation every opposite fact is very important to keep the neutral point of view. My article reviewed another opposite facts from other sources also. The current state of Graph isomorphism article is very incomplete. (For example, I can not find the word "automorphism" in this article. I think, you know that "nauty" means "no automorphism, yes?".) A few references to special cases (trees, planar graphs), to non-deterministic algorithms and a few common words about specific cases are not serious arguments to keep the neutral point of view. Because you will not read my article the discussion about it is not serious. Also I note again and again you use mixing instead of strong arguments. For example, you wrote: "I mentioned the amount of 95,000,000 because your edit included this figure. I am glad to see that you now agree that this is not relevant." However, I had written: "I think, that inspite of 93 M >> 2M, this 2 M set is hardly relevant as well." Another example, again and again you do not want to hear "what this "slight" dependency means", please, compare: "If a function f(n) can be written as a finite sum of other functions, then the fastest growing one determines the order of f(n)."(Big O notation#Properties) Of course, my case is more complicated, because function f has a few arguments (I illustrated similar approach to computational complicity by example from Lipski’s book.) But again, let’s stop this discussion about my article, because you will not read this article, and let’s continue discussion about Graph isomorphism article. Now, in the result, we can consider that we have different points of view. To keep the neutral point of view I insist on addition of this my point to the Graph isomorphism article. Last time I edit a lot of Wiki articles and nowhere else I have similar problem like here. For example, please, see Comparison of Pascal and C: there is very hard situation in this article edition - the first part of editors dislike C (like me), another part dislike Pascal. Anyhow, the stable improving process is obvious, in contrast with Graph isomorphism article, its context seems to be frozen and the current context looks like a resource for the myth distribution, which myth I noted at the beginning of this my message.

Finally, the "reason" "that the medium of publication is not a reliable source for graph theory" is absurd. For example, recently I added a reference to Bull. Chem. Soc. Japan into another graph theory article, and nobody said something against. I think you know that unfortunately not all graph theory problems are interesting for practical applications as well as for other scientific areas. From other side, some mathematics do not want to recognize the graph theory as a real mathematical area. And this situation is very hard problem for many graph theory specialists. So, every graph theory application has significant importance for graph theory status. Also, historically, outside ideas have significant importance for graph theory progress.

You wrote: "I am sorry to have to criticise the result you published" – No problem, you did not criticise the result – you did not read my article ;)--Tim32 11:19, 12 November 2007 (UTC)

  • I don't know where you get that "the majority of mathematics (sic)" considers GI to be NP-complete, but the wikipedia article certainly doesn't share this point of view; it states that this is unknown.
  • 'Hardly relevant' means 'nearly irrelevant'. You probably agreed with me without intending to.
Regards, Phaunt 14:06, 12 November 2007 (UTC)
  • "[…] wikipedia article certainly doesn't share this point of view; it states that this is unknown" – common words only, like following: "In both organic chemical research and circuit design it is important to build databases of graphs"(Graph isomorphism) there is no example for and reference to the organic chemical research, where would be important to build databases of graphs. But this is not too simple: many chem. databases ignore GI problem ;)
  • Sorry for mistake: I wanted to say "very relevant". So, I disagreed with you: this 2 M set is very relevant as well.
  • No more? Very "detailed" reply! You prefer to play words games, rather than to read small paper to ask interesting (for Wiki) questions :-(

Regards,--Tim32 18:47, 12 November 2007 (UTC)

I am not interested in pursuing this debate, as I stated above. Best regards, Phaunt 22:18, 12 November 2007 (UTC)
  • In 8 November 2007, Phaunt wrote: "First off, take it easy and remain civil". Now I see, his original understanding of these concepts. Sorry for that.
  • I had written: "I can not find the word automorphism in this article", just the next day this word was added. - Perhaps in the result of this discussion, perhaps not. Anyhow I am glad to see this improvement.

--Tim32 09:08, 14 November 2007 (UTC)

Applications

"In both organic chemical research and circuit design it is important to build databases of graphs"

-Inorganic chemical compaunds are too simple to use GI test!--Tim32 10:01, 14 November 2007 (UTC)

What? Inorganic molecules can be complex too, and are routinely searched using graph-based algorithms (for example, using Scifinder or the Cambridge Structural Database). --Itub 11:28, 15 November 2007 (UTC)

Please, give a reference. I am focused in organic chemistry problems and may not know last achievements from other chemical areas. Yes, inorganic molecules can be complex as well, but very often elemental composition is sufficient: NaCl, KSCN, K3[Fe(CN)6] etc. Anyhow, organic compounds are more obvious objects for GI-testing.--Tim32 12:17, 15 November 2007 (UTC)

There is no fundamental difference between organic and inorganic molecules, and no need for a reference. As I said, both of the chemical databases I just mentioned have many thousands of inorganic molecules and use graph representations of them. Inorganic molecules do have structure, even Fe(CN)6! And that's without even getting into the huge variety of boron and silicon compounds, for example. --Itub 13:11, 15 November 2007 (UTC)

You wrote: “There is no fundamental difference between organic and inorganic molecules, and no need for a reference. As I said, both of the chemical databases I just mentioned have many thousands of inorganic molecules and use graph representations of them.” Does it mean that you have no reference, and it is your own idea only? The Chemical Abstracts printed in paper has a lot of organic and inorganic compounds, but it does not use GI-test to find any. CAS-online uses SMILES. It is canonical notation to avoid GI-testing, generally, for organic compounds. Majority of inorganic compounds is very simple, and standard chemical notations are sufficient to avoid GI-testing also. Yes, there are boron and silicon compounds, which molecules have many atoms, but these are very special cases and I am not sure that GI-testing is necessary for them. For example, biochemical molecules seem more complex rather than usual organic molecules studied by classical organic chemistry. But there are special notations for biochemical systems, and as a rule GI-testing is not necessary for biochemical database. Again, have you any reference?--Tim32 10:39, 16 November 2007 (UTC)

Do you have one? The point that inorganic chemistry databases exist and use graph isomorphism is so blatantly obvious that you are the one who should have to provide a reference for your extraordinary claim. --Itub 11:06, 16 November 2007 (UTC)
  • Note, please, I did not use words like "blatantly".
  • You wrote: "The point that inorganic chemistry databases exist and use graph isomorphism" -- I do not understand what point do you mean? I do not know what reference I have to give you.
  • I note, you have no reference, so the statement that inorganic chemistry databases uses GI-test is your idea only.---- Tim32 (talk) 17:50, 16 November 2007 (UTC)
Do you have a reference for your idea that GI can only be used for organic molecules? ---- Itub (talk) 17:55, 16 November 2007 (UTC)

I had not idea "that GI can only be used for organic molecules". The GI-testing may be used for very simple graphs also. But I am not sure that it had been used REALLY. You must prove it, if you want. ---- Tim32 (talk) 18:19, 16 November 2007 (UTC)

Oops, I reversed meaning

In my last edit, I committed a "typo" that reversed my meaning. I meant to say that the earlier version implies that P is not equal to NP. BTW, I am surprised by the flaming associated with this article. Such things are usually reserved for controversial articles, such as those associated with global warming. Vegasprof (talk) 10:05, 5 January 2008 (UTC)


One reference

I am quite a neutral reader and I don't know much about the rules of Wikipedia. But it seems obvious to me that it is simply unjust for a scientist, whoever he or she was, to advertise his or her own article in an encyclopedia. A fair scientist should attract attention through the quality of his or her scientific work. Even more is it unjust to advertise a work without agreement of most of the (very professional) editors. I know that Wikipedia has a good means to ensure democracy inside. Meanwhile, I am surprised to see the article in question as the first reference and even in blue - as an outsider I would be made to think that this article is the most important in the area. — Preceding unsigned comment added by 129.67.117.253 (talk) 01:57, 7 January 2008 (UTC)

This unsigned message looks like clone writing.--Tim32 (talk) 12:31, 17 January 2008 (UTC)
You mean a WP:SOCKPUPPET, I assume? Phaunt (talk) 12:46, 17 January 2008 (UTC)

Friedland, January 2008

For the record: On January 2, 2008, Shmuel Friedland submitted a paper "Graph isomorphism is polynomial" to arxiv.org, see arXiv:0801.0398v1. Friedland is a mathematician with more than 100 publications in peer-reviewed journals. Claims about this paper were added to our page on Jan 3.

However, Friedland replaced his arxiv paper by a new version, this one titled "On the graph isomorphism problem", see arXiv:0801.0398v2. This new version seems to retract the original claim. So I think that his paper should not be mentioned in the article -- at least for the moment. If it turns out to be an important step towards determining the complexity, we should mention it, of course.

arXiv.org also contains an earlier paper "A Polynomial Time Algorithm for Graph Isomorphism" by Reiner Czerwinski, arXiv:0711.2010v3. Unlike Friedland, Czerwinski has no refereed publications in mathematical journals so far. (Or possibly one?) Czerwinski quotes a 2005 paper by Trofimov and Smolenskii in the "Russian Chemical Bulletin" (sic), and claims that already that article contained a "program for graph isomorphism with polynomial run time".

Aleph4 (talk) 10:09, 8 January 2008 (UTC)

This is only a way for scientific progress!;)Only this way is possible... --Tim32 (talk) 12:21, 17 January 2008 (UTC)
Please, let us not use the ad hominem "has many publications" argument as a tool for assessing the quality of a paper or (dis)crediting the author... 87.64.17.84 (talk) 09:34, 24 April 2008 (UTC)
For the record: M.Trofimov modified his recursive GI algorithm (M.I.Trofimov,E.A.Smolenskii, Russian Chemical Bulletin, Vol. 54, 2005, pp. 2235-2246. http://dx.doi.org/10.1007/s11172-006-0105-6), which had been noted here.
1) It was adapted for all graphs (not only for molecular graphs);
2) Iterative version was implemented;
3) Complexity of this version is O(n^4).
The article was sent to well-known sci. journal; as soon as it will be printed I’ll add the link.--Tim32 (talk) 18:43, 30 September 2008 (UTC)
  • And as soon it will be added, I will delete it until you provide an independent reference which attests the notability and correctness. Who the heck is this Trofimov? What's his international scientific recognition? Why his stuff deserves place in encyclopedia? `'Míkka>t 19:00, 30 September 2008 (UTC)

The absurd reason that looks like vandalism against NPOV

“Please do not use "vandalism" to describe edits that are clearly in good faith, as you did when reverting this edit. It is a violation of our policies and guidelines on assuming good faith and civil behavior. —David Eppstein (talk) 22:12, 16 January 2008 (UTC)”

"self-promotion of ref to an insignificant paper which adds nothing to the article" is absurd reason, you should prove before that this is "insignificant paper" firstly for chemistry and secondly for graph theory. This is not task for Wiki editors and nobody here should do similar proving and claming (Wiki editors are not official experts), but everybody has to keep the neutral point of view: "NPOV is absolute and non-negotiable", so when anybody deletes a reference to opposite view this action looks like vandalism. I have written a lot for Wiki, and I write only items about I have professional knowleges. So, I use references to my papers (I have written more than 100) as well as to other papers. There is no rule in Wiki against, hence "self-promotion" is absurd reason. There are a lot of references to my papers in Wiki and nowhere else I heard about "self-promotion"!
Not long ago I wrote you that you deleted one link to arxiv (because it “is not peer-reviewed”) and added another link to the arxiv and that it seems that your criteria of notability is too original. It seems now you remember this incedent…;)
Also not long ago I wrote to User:Mikkalai: “You wrote the Hosoya index article just after I had inserted its definition to the matching article…” It seems now he remember this incedent…;)
--Tim32 (talk) 12:06, 17 January 2008 (UTC)
Wikipedia is not a collection of bibliographical references to various scientific articles. The goal of a wikipedian is to add article content. Please explain which content was added by this added reference. The existing link was to a whole book specifically devoted to the particulat application in question and I highly doubt that the reference to the article adds anything but self-promotion of the author. And by the way what is your problem with Hosoya index? Instead, I do remember a long-lasted and insistent promotion pushing right here, in Graph isomorphism. `'Míkka>t 20:22, 17 January 2008 (UTC)
It is well known, that every similar book is based on articles, which articles had been printed before book writing process. Also, it is well known that book writing and printing are very long processes, so it is not surprising that no book is capable to include the newest info. The book you mention is quite suitable as a link to some classical approaches, also it describes some new ideas about the subject. I am do not agree with all comments from this book and my results prove it. The article, I added as second reference, adds significant info, which could not be inserted into the book, because this book was printed in 2005 and the article was printed in 2005. There is 10 pages in the article and if you want to understand details, then read it (or did you seriously think that I must to tell you all this 10 pages here? :). But, first of all, your mistake is that you claimed that the big article printed in well-known scientific journal by Springer is not significant for its general subject! that it has no new important results and so on. This your contradiction official experts (who inspected this article before printing) seems absurdity. Moreover this article is final article for 20 years original investigations which had been done in well-known N.D.Zelinsky Institute of Organic Chemistry of Russian Academy of Science, this article also concentrated results from many previous articles written by my colleagues and me (see list of references in the article). And nobody has a right for such claims without very significant proves. Think a little about!--Tim32 (talk) 15:48, 18 January 2008 (UTC)

Wow! —David Eppstein wrote that big article printed in well-known scientific journal by Springer is "non-notable paper" - is it vandalism?--Tim32 (talk) 17:32, 18 January 2008 (UTC)

It's clearly a reliable source — it's a published, refereed, scientific paper. But that's not the same as being important enough to add a reference to it to this article, among the (roughly) 6000 papers on graph isomorphism listed by Google scholar. —David Eppstein (talk) 18:11, 18 January 2008 (UTC)

Where did you find 6000 published papers on the subject of graph isomorphism? In google? Every graph theory textbook has a few words about graph isomorphism. The number of original papers may be less. But this is not reference to graph isomorphism problem!!! This is reference to its chemical application! Only this application is noted and only one another reference is used in Graph isomorphism:

“The graph isomorphism problem arises in a variety of practical applications. For example, in cheminformatics and in mathematical chemistry, graph isomorphism and other graph matching techniques are used to identify a chemical compound within a chemical database.” [1] [2] [1] Christophe-André Mario Irniger (2005) "Graph Matching: Filtering Databases of Graphs Using Machine Learning", ISBN 1586035576 [2] M.I.Trofimov, E.A.Smolenskii, Russian Chemical Bulletin, 2005, Vol. 54, 9, 2235. (http://dx.doi.org/10.1007/s11172-006-0105-6)

And I have already written in Talk:Graph isomorphism “It is well known, that every similar book is based on articles, which articles had been printed before book writing process. Also, it is well known that book writing and printing are very long processes, so it is not surprising that no book is capable to include the newest info. The book you mention is quite suitable as a link to some classical approaches, also it describes some new ideas about the subject. I am do not agree with all comments from this book and my results prove it. The article, I added as second reference, adds significant info, which could not be inserted into the book, because this book was printed in 2005 and the article was printed in 2005.”

I can add that there are differences ([1] vs [2]) for following significant problems: planar graphs in organic chemistry and regular graphs in organic chemistry. It is important enough to add a reference to it to this article!!! Stop edit war and read article by Trofimov and Smolenskii! Note, please, you will need some skills in organic chemistry...--Tim32 (talk) 21:26, 21 January 2008 (UTC)

I reverted the edits of Tim32. It seems his edits are used mainly for self-promotion and in any case we are in no hurry to integrate very recent research (2005) into wikipedia. MathMartin (talk) 13:04, 22 January 2008 (UTC)

It seems you did it mainly for self-promotion!--Tim32 (talk) 14:41, 22 January 2008 (UTC)

Edits by Tim32

User Tim32 recently edited the section ==Applications== and added the following text

However, for non-trivial research in organic mathematical chemistry effective algorithm for filtration of data containing information on the structures of organic molecules based on strong isomorphism testing may be quite necessary.

with a citation to

M.I.Trofimov, E.A.Smolenskii, Russian Chemical Bulletin, 2005, Vol. 54, 9, 2235. (http://dx.doi.org/10.1007/s11172-006-0105-6), to the article:

I have removed the sentence and the citation from the article. Tim32 please clarify what this sentence means (what is strong isomorphism testing, what is filtration of data), and explain why the citation is important enough to be included in the article. David Eppstein, Míkka and myself removed the citation in the article several times because it does not seem notable and relevant enough to be included. As the cited paper is pretty recent (2005) Tim32 has to supply sufficient proof of its importance, which he has not done so far, and if its importance is unclear it should not be included. MathMartin (talk) 13:59, 23 January 2008 (UTC)

Whitney isomorphism and hypergraphs

Text below is reposted from my talk page; edited for brevity. linas (talk) 17:51, 24 July 2008 (UTC)

Linas - it seems you wrote on the graph isomorphism page that "The Whitney graph theorem can be extended to hypergraphs." Do you have a reference for this claim? I've found people mean a lot of different things when they say hypergraph, and I'm having trouble recreating the conditions one should assume to get a nice correspondence like Whitney does for graphs.

Thanks, Mica (talk) 15:08, 24 July 2008 (UTC)

Hi Mica,
"The Whitney graph theorem can be extended to hypergraphs." is a one-sentence summary of a large chunk of an article from the book by Claude Berge, Dijen Ray-Chaudhuri, "Hypergraph Seminar, Ohio State University 1972", Lecture Notes in Mathematics 411 Springer-Verlag. If I remember correctly, its in the very first article, by Berge himself, in the third section. The claim that this somehow generalizes the Whitney thm is Berge's own; I've just paraphrased. linas (talk) 17:14, 24 July 2008 (UTC)

Number of vertices

A question regarding the definition given in the article:

  • In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H such that any two vertices u and v of G are adjacent in G if and only if ƒ(u) and ƒ(v) are adjacent in H.
    • Thus, graph H could possible have more vertices than graph G, with these spare vertices being unconnected to any other vertex, right? --Abdull (talk) 12:09, 28 July 2008 (UTC)

No. A bijection has to be, in particular, surjective. — Emil J. (formerly EJ) 12:23, 28 July 2008 (UTC)

Whitney's theorem

I believe the one exception (recently removed) was important, but that the theorem was stated incorrectly in this article - I'm attempting to recover the original paper. Dcoetzee 23:29, 31 July 2008 (UTC)

Okay, I figured this out now - the statement "G and H are isomorphic if and only if their line graphs are isomorphic" requires a single exception, as explained at line graph, because the line graphs of K3 and K1,3 are identical (they are both K3). Adding the "with the same number of vertices" condition eliminates this special case, but also understatements the generality of the full theorem. Dcoetzee 23:46, 31 July 2008 (UTC)

which reduction

Given that the whole point of GI is to make a complexity class from the graph isomorphism problem (g.i.p.), it is absurd to use a notion of GI-completeness which does not make g.i.p. GI-complete (or rather provable to be complete given the present state of knowledge). Defining GI-completeness using many-one reductions suffers from this very problem: for example, the complement of g.i.p. is in GI, but if it is many-one reducible to g.i.p., then g.i.p. (and the whole of GI) is in NP ∩ coNP, which is not known to hold.

As GI is itself defined as the closure of g.i.p. under Turing reductions, it is only natural to define GI-completeness using Turing reductions. At any rate, that's what one can find in the literature, I'll put a reference in the article. — Emil J. (formerly EJ) 10:05, 5 August 2008 (UTC)

I was just guessing - I don't know which definition is used in the literature (a reference would be welcome). However, Turing-reducibility is strictly more general than many-one reducibility, so using Turing reductions would only make GI-complete larger. In particular, the problem you described with graph nonisomorphism being GI-complete appears to hold for Turing reductions, but not necessarily for many-one reductions, which is the opposite of what you're claiming. Dcoetzee 04:26, 11 August 2008 (UTC)
I don't understand at all what you are saying. Using Turing reductions indeed makes GI-complete larger, which is perfectly consistent with the problem I was describing, namely that graph isomorphism is not GI-complete for the more restrictive many-one reductions, but it is (as expected) GI-complete for Turing reductions. Also, what do you mean by "reference would be welcome"? I already did put a reference in as promised. — Emil J. (formerly EJ) 09:51, 11 August 2008 (UTC)
My apologies, I didn't review the history; your definition is in fact the standardly-used one and I accept it. Your original argument is still unclear to me though; it's true that it's not known if the complement of GIP reduces many-one to GIP, but the definition I proposed would not imply this (unless you assume the complement of GIP is GI-complete, not just that it's in GI). It seems obvious that any problem is many-one reducible to itself by a trivial reduction, so GIP would be GI-complete under either definition. Am I missing something? Dcoetzee 10:49, 11 August 2008 (UTC)
But the fact that the graph isomorphism problem is reducible to the graph isomorphism problem does not in any way imply that every problem from the GI class is reducible to the graph isomorphism problem. GI-completeness means the latter, so it is not necessarily trivial, and it may depend on the reduction being used. — Emil J. (formerly EJ) 11:01, 11 August 2008 (UTC)
I see now, of course you're right. Your original argument makes perfect sense. I don't know what I was thinking. :-/ Dcoetzee 13:53, 11 August 2008 (UTC)

Is a graph finite?

Are the graphs considered in the isomorphism problem assumed to be finite? (Usually graphs aren't). Otherwise I cannot imagine the problem would even be in NP.--Roentgenium111 (talk) 23:01, 22 September 2008 (UTC)

Yes. Normally, in computational complexity theory the input data for algorithms must be specified in a finite way. I added the word "finite" into the article. Thanks for bringing an attention to it. While the detail is minor and assumed by graph theoretists without saying, an outsider may be left wondering. `'Míkka>t 23:15, 22 September 2008 (UTC)

Regular graphs are very difficult

User Tim32 keeps inserting statement that "regular graphs are very difficult for GI", citing a reference to an obscure publication by people unknown in graph theory. I find this statement dubious and request to provide proofs why they are "very" difficult and in what mathematical sense. `'Míkka>t 19:44, 30 September 2008 (UTC)

Regular graphs are very difficult for many GI algorithms! See, G.Gati, Further Annotated Bibliography on the Isomorphism Disease, J. Graph Theory 3(1979), 95, for example! Do you need more ref-s??? ;)--Tim32 (talk) 19:41, 30 September 2008 (UTC)

That's exactly why I requested a ref from a respectable source. Please write clearly accordingly and provide the correct reference. Please cite what exactly Gati wrote, since I don't believe your phrasing is correct. `'Míkka>t 19:46, 30 September 2008 (UTC)

Please, see the nearest link: User_talk:David Eppstein#Is_graph_isomorphism_in_P?:"it seems likely that for some kinds of graphs, such as distance-regular graphs, it never forms more than one equivalence class and so fails either to terminate or to identify the isomorphisms. —David Eppstein (talk) 04:11, 25 May 2008 (UTC)". But why I believe your phrasing is correct? Please, cite where exactly wrote that regular graphs as simple for all GI algorithms as other graphs.--Tim32 (talk) 20:20, 30 September 2008 (UTC)

Regular graphs and distance-regular graphs are way not one and the same. And by the way, I wasted an hour of my time to go to the libray to check the article of Gati only to find that nowhere it says that regular graphs are difficult. You have proven your scientific dishonesty and further discussion with you will be carried out only if you provide exact quotations for statements you make. In other words, the discussion will be not with you, but with sources you quote verbatim. `'Míkka>t 20:53, 30 September 2008 (UTC)

User:Mikkalai wrote in the article Graph isomorphism:

"dubious reference and deletion of my changes. Please provide a reputable ref.", about:

"Regular graphs are very difficult for such testing and many of them are very important for chemistry (for example, Cyclohexane, Benzene, Cuneane, Dodecahedrane etc.), but their part among chemical compounds is small, and decreases with increasing of number of vertices<--ref>M.I.Trofimov, E.A.Smolenskii, Russian Chemical Bulletin, 2005, Vol. 54, 9, 2235. (http://dx.doi.org/10.1007/s11172-006-0105-6)<--/ref>."

Is Russian Chemical Bulletin reprinted by Springer-Verlag is not "a reputable ref."? Is it "dubious reference"? Is User:Mikkalai is expert for such statements?--Tim32 (talk) 21:31, 30 September 2008 (UTC)

A Chemical bulletin has no say in computer science, unless the results are confirmed by computer scientists. By the way, how exactly Trofimov/Smolenskii substantiate the claim about "very difficult"? Did they run benchmarks for a wide range of algorithms and classes of graphs? `'Míkka>t 21:54, 30 September 2008 (UTC)

PS. Again: Please, cite where exactly wrote that regular graphs as simple for all GI algorithms as other graphs--Tim32 (talk) 21:31, 30 September 2008 (UTC)

Why? I dont' write this in wikipedia article. `'Míkka>t 21:54, 30 September 2008 (UTC)

PPS. "Regular graphs and distance-regular graphs are way not one and the same"(User:Mikkalai ) -- :))) "You have proven your scientific dishonesty..." (User:Mikkalai ) -- !!! no remarks!!! --Tim32 (talk) 21:31, 30 September 2008 (UTC)

What is that supposed to mean? Do you want to say that you were scientifically honest when you quite sarcastically referred to the article by Gati without knowing what is written there and which says nothing to the point in question? `'Míkka>t 21:54, 30 September 2008 (UTC)
  • Gati wrote a good article, and I do know this article. If you are unable to understand it-- it is your own problem, sorry! You did not find "regular" in this article? Sorry again! Let you try to think a little!! About vertex degree, for example... Try to find "regular" in this page! Maybe you printed any original article to see your point? ;)--Tim32 (talk) 22:27, 30 September 2008 (UTC)
  • PS. You wasted an hour of your time to go to the libray to read Gati, I spent 0.25 hour of my time to find in Internet:
  • "A number of authors (probably, the first were Corneil and Gotlieb [52]; seethe annotation in [I01]) assert that their algorithms have a polynomial complexity for graphs not containing strongly regular subgraphs." "After the papers [90, i01, iii] in which it was said that strongly regular graphs form a difficult class for GI algorithms" V. N. Zemlyachenko, N. M. Korneenko, R. I. Tyshkevich,GRAPH ISOMORPHISM PROBLEM, Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 118, pp. 83-158, 1982.
  • Hope it helps you to understand this fact which is well-known for real specialists in graph theory. Another fact that "their part among chemical compounds is small, and decreases with increasing of number of vertices" (M.I.Trofimov, E.A.Smolenskii) is not well-known and has important practical sense. Sorry I have no time to get you more citations. You can find a lot in Internet yourself. Hope you will restore this "dubious reference", ASAP. And, pls, think before to cry about somebody professional level. (I would be able to estimate your level only via your original article in any sci. journal). ;)--Tim32 (talk) 01:41, 1 October 2008 (UTC)

It does not help you cause to be so condescending. Please be more civil. —David Eppstein (talk) 02:11, 1 October 2008 (UTC)

  • Ok! But, please, note this was Revision of 14:14, 24 January 2008 and User:Mikkalai saw it! Yesterday (30 September 2008) he disliked my comment here, and just the moment he deleted this Revision of 14:14, 24 January 2008! Please, see history!!! Also User:Mikkalai wrote here at start: "Who the heck is this Trofimov? What's his international scientific recognition?" and also "dubious reference and deletion of my changes. Please provide a reputable ref." Maybe he must be more civil as well? Please, compare my words and his words. --Tim32 (talk) 12:43, 1 October 2008 (UTC)
I looked at the paper by Zemlyachenko et al. (doi:10.1007/BF02104746), and right after the first sentence quoted by Tim32, the authors write "However, if these authors were true, then there would exist a GI-algorithm of polynomial complexity (see Sec. 16)". And in Section 16, they explain that if we find an algorithm with polynomial complexity for graphs not containing strongly regular subgraphs, then we can use it to construct an algorithm with polynomial complexity for all graphs. So in that sense strongly regular subgraphs are not more difficult (if I understand it correctly). Nevertheless, it does seem that many researchers feel that regular graphs are the hardest in practice. So why don't you try to write a text which has both facts?
And I agree that both of you should strive harder to work together. Tim32, if you found Gati's text on the internet, why don't you provide a link? And why don't you be more precise on where he talks about regular graphs? Mikkalai, accusations of scientific dishonesty only inflame the situation. Please don't do that again. -- Jitse Niesen (talk) 11:41, 1 October 2008 (UTC)
  • Jitse Niesen wrote "it does seem that many researchers feel that regular graphs are the hardest in practice",yes! But it is not feeling only, it is fact also (and generally)! There are many reports in Internet that well-known Nauty has problems with regular graphs etc. I am very surprised that these facts are not known here. The J. of Graph Theor. has copyright for Gati's text, if you have login to JGT site, then you can find it there. But I have already said sorry for this example, I think that regular graph problem is obvious from that text. For example, is it obvious that GI for trees may be found faster than for graphs with rings? Also is it obvious that if the graph vertices all have different degrees, then GI may be found by very fast and trivial algorithm? (for example, see top of this page) Is it obvious that a lot of local topological indices will be different for different degrees? ;) But the noted text by Trofimov&Smolenskii was in section about chemical applications of GI. "Academic and peer-reviewed publications are highly valued and usually the most reliable sources in areas where they are available" (See, wp:source.) Russian Chemical Bulletin is Academic (Russian Academy of Sci.) and reviewed journal, in chemistry area. This ref. is quite sufficient! If anybody here has an original idea that this is "dubious reference" he/she has to print it in any sci. journal before edit GI article! --Tim32 (talk) 13:40, 1 October 2008 (UTC)
  • Sorry, Jitse Niesen has a wrong impression. Some researchers do repeat some hearsay, and I will not comment on the smartness of these researchers. We are talking mathematics here, not political science: if a statement in maths is made, you must have a proof. Now, I am repeating my request: please provide a reference which has the following:
    • definition the meaning of the word "difficult"
    • Proof that regular graphs are difficult (mathematical or experimental)
In some cases in mathematics opinions about possible facts do count. Mathematicians call such an opinion a hypothesis. Any undergrad may pose a bunch of hypotheses. Those which have significant impact on maths are treated with the same respect as theorems. The statement that "regular graphs are difficult" is not. The fact that it is repeated in some obscure articles by persons with little credentials in graph theory bears little weight. `'Míkka>t 15:47, 1 October 2008 (UTC)

>definition the meaning of the word "difficult"

For example, see "Because of this, it is often said that the NP-complete problems are "harder" or "more difficult" than NP problems in general." (NP-complete#Formal overview)

regular graphs are not "difficult" in this sense. `'Míkka>t 17:21, 1 October 2008 (UTC)
  • why? are you sure? Proof it! You wanted meaning of the word "difficult"? Or something else? I do not find "regular graphs" in your request: "definition the meaning of the word "difficult""--Tim32 (talk) 19:06, 1 October 2008 (UTC)

>Proof that regular graphs are difficult (mathematical or experimental)

Experimental proof -- see, noted article by Trofimov&Smolenskii.

The noted article talks about "total of 95,000,000 molecules containing up to sixty carbon atoms." - graphs with several hundreds of vertices are trifle for modern computers. LVS jobs routinely run graphs with tens of millions vertices today. `'Míkka>t 17:21, 1 October 2008 (UTC)
Anyway, since the article is not freely available, please write exactly what proof they presented that regular graphs are difficult in whatever sense. `'Míkka>t 17:21, 1 October 2008 (UTC)

>The fact that it is repeated in some obscure articles by persons with little credentials in graph theory bears little weight

The list of persons "with little credentials in graph theory bears little weight":

1)M. I. Trofimov 2)E. A. Smolenskii 3)V. N. Zemlyachenko 4)N. M. Korneenko 5)R. I. Tyshkevich 6)R. T. Faizullin 7)A. V. Prolubnikov 8)Jitse Niesen 9)David Eppstein

Are you sure? You must proof it! --Tim32 (talk) 16:43, 1 October 2008 (UTC)

And which exactly work in graph theory by Jitse Niesen you are going to cite in the article "Graph isomorphism"? `'Míkka>t 17:21, 1 October 2008 (UTC)
By the way Zemlyachenko et al. did not claim that "regular graphs are difficult". `'Míkka>t 17:21, 1 October 2008 (UTC)
  • They noted Corneil and Gotlieb etc. So we may add to the list:
  • 10)Corneil 11)Gotlieb
Jitse Niesen has already pointed out that this whole debate was sparked by ambiguity around the word "difficult". Based on the source cited by Jitse Niesen, it's pretty clear that a polynomial-time reduction exists from the GI problem for arbitrary graphs to the GI problem for graphs not containing strongly regular subgraphs. Polynomial-time reduction is a standard definition of (theoretical) difficulty in computational complexity theory, so it's okay to say that in theory the GI problem for strongly regular graphs is not any more difficult than that for regular graphs. On the other hand, experimental results show that on average regular graphs take longer to solve in practice. There is no contradiction between these two statements because they use a different notion of "difficult". This really is a WP:LAME edit war, albeit an academic one. VG ☎ 20:05, 1 October 2008 (UTC)
Also, one or more editors here need to refrain from editing the other editors' posts, since it's bloody impossible to follow the conversation above! VG ☎ 20:07, 1 October 2008 (UTC)

VG wrote: "On average regular graphs take longer" - that's the whole point of this wrangle: I request a reference to the article which describes experiments that lead to the above conclusion. I am repeating: a reference to a hearsay is not admissible. This is mathematics. `'Míkka>t 22:19, 1 October 2008 (UTC)

Anyway, I've just restored the disputed phrase in the "Applications" section, but I am waiting for claification of my doubts, for some reasonable time. `'Míkka>t 22:24, 1 October 2008 (UTC)

Comment. Tim32 seems to have the same email address (shown on his user page) as the main author of the paper (M. I. Trofimov) [1] which supposedly provides the experimental info. So, there is a potential WP:COI here. I'm not saying that his identity discredits the paper or his position, but I'd be more careful to verify it from other sources. I cannot read the paper myself; I have access to one of the largest academic libraries in the U.S. (University of Maryland), but Russian Chemical Bulletin is no longer stocked there (since 1998), and no on-line access was purchased for that journal. So, it's fair to say that this isn't a mainstream journal (anymore). VG ☎ 23:13, 1 October 2008 (UTC)
  • Yes, some time ago I wrote on this page that my name is Michael I. Trofimov and I am author of this paper. And of course I write in Wiki only items that I studied. As a rule I printed something about these items (totaly I printed about 100 articles). It is very strange that your library has not on-line access to Springer-Verlag web-site in "full text" mode. There are many important journals and books on this site. "Within the science, technology, and medicine sector, Springer is the largest book publisher, and second-largest journal publisher worldwide"(Springer Science+Business Media) Please, send me email and we will think together how to help you.
  • A few words about this journal. The editorial of Russian Chemical Bulletin is based in N.D.Zelinsky Institute of Organic Chemistry of Russian Academy of Sci., Moscow, Russia. It is the largest and the most important Russian research institute in Organic Chemistry area. There are Russian and English issues of the journal. The Springer-Verlag is publisher of English issue. You can find a lot of links to this journal in English and in Russian Wiki. (BTW, every person can buy on-line copy of any article from this journal via Springer site or via Russian editorial site.)--Tim32 (talk) 11:37, 2 October 2008 (UTC)
Yes, graph isomorphism on regular graphs is hard, in the sense that we already have a reference that shows it's GI-complete (although the degree must be unbounded, since graphs of bounded degree have a polytime algorithm). On the other hand, it's quite a more difficult issue to empirically determine what classes of graphs give existing heuristic isomorphism algorithms difficulty. This is a worthy subject for publication, but I'm not aware of any publication on it. Dcoetzee 07:39, 2 October 2008 (UTC)

.

  • Again: is it obvious that GI for trees may be found faster than for graphs with rings? Also is it obvious that if the graph vertices all have different degrees, then GI may be found by very fast and trivial algorithm? (for example, see top of this page) Is it obvious that a lot of local topological indices will be different for different degrees?--Tim32 (talk) 11:51, 2 October 2008 (UTC)
    • No not obvious. Yes, obvious. No, not obvious. In any case, I don't see how is it related to my request for your confirmation (in a form of a qutation or a decent summary) of a proof that regular graphs are "very hard". `'Míkka>t 14:47, 2 October 2008 (UTC)
  • Thank you for you interest to my article, but sorry, I can not copy here 5 tables and 5 pages of the text, also full article may be necessary to understand these results (12 pages). Any short citation would be out of context, and may be misunderstood, for example, we noted that it is not fundamental difference, i.e., for example, average time ~exp(n) vs. n^5 is fundamental for theory, and 5n^5 vs. 0.5n^5 is not fundamental in theoretical sense, but may be very important for practical usage, for example, to support chemical database.
  • Your answers to my questions:
  • Q: is it obvious that GI for trees may be found faster than for graphs with rings?
  • A: No not obvious.
  • Remark: Maybe it is not obvious. But there are well-known very fast algorithms for tree GI.
  • Q: is it obvious that if the graph vertices all have different degrees, then GI may be found by very fast and trivial algorithm?
  • A: Yes, obvious.
  • R: very important answer for many irregular graphs.
  • Q: Is it obvious that a lot of local topological indices will be different for different degrees?
  • A: No, not obvious.
  • R: In trivial case local topological index is vertex degree.
  • PS "Q: is it obvious that if the graph vertices all have different degrees, then GI may be found by very fast and trivial algorithm? A: Yes, obvious." This means that for simple backtracking algorithm, which algorithm tests only vertex pairs with the same degree: if all vertices have different degree, then complexity of this algorithm is n; if all vertices have the same degree (regular graph case), then n!. Also, if k vertices have degree deg(k), and other vertices have degree deg(other), then k!(n-k)!. And also, if k vertices have degree deg(k), m vertices have degree deg(m),…, i vertices have degree deg(i), then k!m!…i!(n-k-m-…-i)!. Because n!> k!(n-k)!>…> k!m!…i!(n-k-m-…-i)!, thus the regular graph case is the most difficult. I do hope this is trivial and quite obvious result as well.--Tim32 (talk) 11:07, 3 October 2008 (UTC)
  • Again! It is your own problem that you have not the both: 1) you have not login to full text in Springer-Verlag web-site 2) you have not $30US to pay Springer-Verlag for the copy of the paper. Really "stupid" (your word) arguments! --Tim32 (talk) 23:52, 11 October 2008 (UTC)


I've asked for Trofimov's paper through ILL; it will take a few days before I get it. As general comment, I think it's okay to cite experimental results from computational chemistry papers in graph articles. UMD faculty that works in graph theory sometimes collaborates with colleagues from the Chemistry department since that's a major application area. So, it's not outlandish that significant experimental results in graph theory are published in Chemistry journals. VG ☎ 15:39, 2 October 2008 (UTC)

There are two red flags with Trofimov's paper:

  1. It is not demonstrated that it is discussed in mainstream community. Yes, significant experimental results are of note. But you selected a wrong keyword to stress: which must be the word "significant". I don't see published claims that Trofimov's paper is "significant". Authors' and wikipedians' opinions do not count. `'Míkka>t 18:43, 3 October 2008 (UTC)
  2. The author shows high proficiency in evading a simple question: how exactly it is shown that "regular graphs are difficult". `'Míkka>t 18:43, 3 October 2008 (UTC)
  • I see you very like the red flag ;-) I also don't see published claims that you words are "significant". Your wikipedians' opinions do not count! :-))))--Tim32 (talk) 23:59, 11 October 2008 (UTC)
    • Unlike you, I am not trying to push my publications into wikipedia aticles. Your remark shows that you have little understanding how wikipedia works: since you are adding text, it is your obligation to substantiate it. `'Míkka>t 18:58, 12 October 2008 (UTC)
    • Unlike you, I did not write anti-encyclopedic article like this jokebook.BTW Have you any publication? ;)--Tim32 (talk) 11:52, 13 October 2008 (UTC)
      • Please learn to use wikipedia. Much as I wanted the glory, the first entry in the history of the jokebook says: (cur) (last) 03:33, July 29, 2006 Mikkalai (Talk | contribs | block) (cut out of Russian joke). Furter, if you care to browse the history of the article Russian joke, 90% of my contribution to it is deletion of jokes. Finally: If you think the article do not fit wikipedia, you are welcome to put it for deletion. `'Míkka>t 14:54, 13 October 2008 (UTC)
    • I'm afraid I concur with Mikka; there's little evidence the source should be treated as credible, although probably "reliable". Even if peer-reviewed, the reviewers would likely be chemistry' experts rather than mathematics experts. As for VasileGaburici's comment above, at best, it would mean the best algorithms known to the chemists take longer (in some sense), probabilisticly, for regular graphs. That's not adequate to make general assertions of mathematical difficulty.
  • Obviously, some methods of determining whether graphs are isomorphic don't work as well on regular graphs. If there were an anti-regular graph, then isomorphism between such could be easily determined. — Arthur Rubin (talk) 01:02, 12 October 2008 (UTC)
    As for "is it obvious that if the graph vertices all have different degrees, then GI may be found by very fast and trivial algorithm?", it's a contrafactual assumption. It can easily be seen (by induction) that it is impossible for an n-point graph to have all possible degrees from 0 to n-1, as the vertex with degree 0 cannot and must connect to the vertex with degree n-1. — Arthur Rubin (talk) 01:07, 12 October 2008 (UTC)
  • The reviewers were experts in Mathematical chemistry area, i.e. experts in graph theory. Can you say the same words ("unreliable source?") about an article from a physical journal? ;) Also, note, please, we are talking about "Applications" section. I.e. about chemical applications. Can you find many sources about chemical applications in pure mathematical journals? For example, in J. of Graph Theory? I'm afraid you are poor informed about mathematical level of modern chemical investigations (another example is Quantum chemistry -- an expert in quantum chemistry should be expert in mathematics as well!).
  • Yes you are right "vertices all have different degrees" should be corrected: let a vertex has (1) degree 1 or (2) different degree >1. GI for such graphs may be found by very fast and trivial algorithm.--Tim32 (talk) 12:59, 12 October 2008 (UTC)
  • PS. BTW I discussed this regular graphs' problem with M. Meringer and S. S. Tratch they are well-known specialists in graph theory and in mathematical chemistry areas. You can find my thanks to them in the article. --Tim32 (talk) 13:19, 12 October 2008 (UTC)
    • All this do not change the fact that you are laborously refusing to provide quotations from the artice in question which supprot the statement you are trying to add into the wikipedia article. `'Míkka>t 18:49, 12 October 2008 (UTC)
I went through the article by Trofimov et al. and I the only thing that could find about the statement on whether regular are more difficult is "Regular graphs are thought to be the most difficult for many algorithms including the graph isomorphism algorithms. However, our tests revealed no fundamental difficulties for this class of graphs." It is quite possible that I missed something, so I'd be interested what VG makes of it. But at the moment I see no reason to keep the statement in our article. -- Jitse Niesen (talk) 19:06, 12 October 2008 (UTC)
Sorry, I still don't have access to the article (ILL is proving slow on this one), so I cannot comment either way right now. VG ☎ 19:19, 12 October 2008 (UTC)
to Jitse Niesen: the statement is out of context my algorithm showed no fundamental difficulties, but you can see difficulties -- compare tables 1-4. Also see about server model (p.2241)--Tim32 (talk) 11:52, 13 October 2008 (UTC)
Just weighing in in support of omitting these claims. No credible source has been provided - this appears to be an overgeneralization of the observation that sets of vertices with distinct vertex degrees can be used to generate equivalence classes for isomorphism. However, there are many other ways to generate equivalence classes, and it consequently seems just as reasonable that there would be a class of regular graphs that have a very fast algorithm for graph isomorphism. I would believe it if someone said that some particular algorithm performs poorly on average for regular graphs, but nobody has advanced a proof of even that much. Dcoetzee 22:11, 12 October 2008 (UTC)
Dcoetzee wrote: "there are many other ways to generate equivalence classes, and it consequently seems just as reasonable that there would be a class of regular graphs that have a very fast algorithm for graph isomorphism." --It is your original idea only. (WP:NOR) Also again, Nauty has problems for regular graphs, see http://amalfi.dis.unina.it/graph/db/papers/benchmark.pdf And also, the info from chemical journal is more important for chemical GI applications (adapted for chemistry) than similar info from pure mathematical journal (not adapted for chemistry). Anyhow, nobody here is able to get a link to opposite view, that regular graphs are not very difficult for chemical applications of GI, so I restore my statement in the article. As soon as you find the opposite link you can add this opposite statement to the article, but you must not delete my link for NPOV.--Tim32 (talk) 11:52, 13 October 2008 (UTC)
Firstly, Wikipedia articles are written by consensus. At the moment, Mikkalai, Arthur Rubin, Dcoetzee and myself are against the sentence that you want to add and only you support it. Thus, it should not go in. That is how Wikipedia works.
Secondly, the sentence you want to put in says "Regular graphs are very difficult for isomorphism testing […]" with a reference to your article. However, your article does not show that regular graphs are very difficult for isomorphism testing; at most, the article shows that regular graphs are more difficult than random graphs for your algorithm (I have no idea what the server model in your paper, that you refer to in reply to me above, has to do with it). The same goes for the paper by Foggia et al., the graphs do show that Nauty has troubles with regular graphs but it also shows that other algorithms like VG2 perform better on regular graphs than on random graphs.
Thirdly, the paper by Zemlyachenko et al. says that strongly regular graphs are not more difficult. Similarly, Spielman says "For a while, the class of strongly regular graphs seemed to capture much of the difficulty of the isomorphism problem. But, in 1980, Babai [Bab80] proved that a simple combinatorial algorithm would test isomorphism of strongly regular graphs in time n^O(sqrt(n) log(n))" (doi:10.1145/237814.238006).
It may be possible to find a formulation that we can agree on. But at the moment, there is just too big a gap between what your paper shows and the statement that regular graphs are very difficult for isomorphism testing. -- Jitse Niesen (talk) 13:53, 13 October 2008 (UTC)
You are misapplying policy. WP:NOR applies only to article content; it is perfectly acceptable to use original research in arguing on a discussion page to discuss why material should or should not be included or whether a source is reliable. I think there is something interesting to say here, but it's much more complicated than the simple overgeneralization that "regular graphs are hard," and brevity does not trump accuracy. Dcoetzee 00:26, 14 October 2008 (UTC)
  • To Jitse Niesen: First of all, is it edit war or discussion? If it is war, then what we talk about here? If it is discussion, then I do not understand is it too necessary to edit and reedit the article, again and again delete and restore the statement about regular graphs before the end of discussion? Because you wrote that you want consensus, I think that it is not war. Hence, would you be so kind to restore and keep the statement about regular graphs in the article until the end of this discussion?
  • You misrepresented the facts and sense of citations:
  • Zemlyachenko, Korneenko and Tyshkevich wrote: “A number of authors (probably, the first were Corneil and Gotlieb [52]; seethe annotation in [I01]) assert that their algorithms have a polynomial complexity for graphs not containing strongly regular subgraphs. However, if these authors were true, then there would exist a GI -algorithm of polynomial complexity (see Sec. 16).” (V. N. Zemlyachenko, N. M. Korneenko,and R. I. Tyshkevich, Graph Isomorphism Problem, Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 118, pp. 83-158, 1982).
  • Foggia, Sansone and Vento wrote: “On more regular graphs, i.e. on 2D meshes, VF2 is definitely the best algorithm: in this case the Nauty algorithm is even not able to find a solution for graphs bigger than few dozens of nodes. In case of bounded valence graph, if the valence is small, VF2 is always the best algorithm, while for bigger values of the valence the Nauty algorithm is more convenient if the size of the graphs is small.”
  • Trofimov and Smolenskii wrote: “Regular graphs are thought to be the most difficult for many algorithms including the graph isomorphism algorithms. However, our tests revealed no fundamental difficulties for this class of graphs.”
  • And also (about the model of server) Trofimov and Smolenskii wrote: “In particular, if database querying is simulated using a random graph generator, we get the situation illustrated by Table 2. Here, the maximum recursion depth and number of iterations are smaller than for the values listed in Tables 3 and 4, because the most difficult cases were not included in the random sets and the probability for difficult cases to be included in the random sets seems to decrease with an increase in x. However, this model is sometimes unrealistic, because certain regular SGs, e.g., cyclobutane, cyclopentane, and cyclohexane, cubane, dodecahedrane, etc. play significant roles in chemistry. One can assume that a server managing a database for a rather long time period can be queried with a query distribution pattern similar to the random model. But these periods will be alternated by shorter but intense periods of high demand for information concerning a small group of structures; the complexity of the processing of such queries by the server will exceed some averaged characteristics. This can be due to, e.g., sensations concerned with the synthesis of a compound from this group. For instance, a pioneering synthesis similar in significance to the synthesis of dodecahedrane will undoubtedly attract the major attention of chemists, which will unavoidably affect the performance of our speculative server. Therefore, in the course of tests particular attention was given to the regular MGs in spite of a small proportion of such graphs among all possible MGs.”
  • Where Table 1 is “Generation of complete sets of graphs with preset number of vertices”, Table 2 is “Comparison of pair sets in 10,000 of random graphs with preset numbers of vertices”, Table 3 is “Comparison of complete pair sets of regular graphs with preset number of vertices and a vertex degree of 3”, Table 4 is “Comparison of pair sets in 5,000 regular graphs with a preset number of vertices and a vertex degree of 3” and Table 5 is “Proportion of regular graphs”.
  • Compare table 1,2,3,4 – you will see that iteration maximum numbers for complete sets of graphs (table 1) and for random graphs (table 2) are not very different, and also you will see that maximum iteration number and the maximum recursion depth are more for regular graphs, but it is not fundamental difficulties, for example for number of vertices 38 we have iteration number=6 (random graphs) vs iteration number=12 (regular graphs). Again, it is not fundamental difficulties in contrast with works by Corneil and Gotlieb, which works were noted by Zemlyachenko (P vs NP). Anyhow why three noted groups of reseachers (Zemlyachenko’s group, Foggia’s group and Trofimov’s group) specially noted regular graphs or strongly regular subgraphs? Why “particular attention was given to the regular graps”? Because “Regular graphs are thought to be the most difficult for many algorithms including the graph isomorphism algorithms”. And we noted that performance of the server model should be estimated by processing of regular graphs. This is very important for many chemical applications of GI.
  • Also on this page I have already described very obvious and trivial theoretical “proof” of this fact. For record I reproduce it again (note, a graph may has loops (edge (i,i)): for simple backtracking algorithm, which algorithm tests only vertex pairs with the same degree: if all vertices have different degree, then complexity of this algorithm is n; if all vertices have the same degree (regular graph case), then n!. Also, if k vertices have degree deg(k), and other vertices have degree deg(other), then k!(n-k)!. And also, if k vertices have degree deg(k), m vertices have degree deg(m),…, i vertices have degree deg(i), then k!m!…i!(n-k-m-…-i)!. Because n!> k!(n-k)!>…> k!m!…i!(n-k-m-…-i)!, thus the regular graph case is the most difficult.
  • Conclusion. As a rule, regular graps are difficult for many GI algorithms. Strong regular graphs and some other special cases are exceptions from this rule. This rule has practical (may be only practical not theoretical) importance for GI applications in chemistry.
  • Your words about consensus “4 vs 1” sound very naive: for example, I can suppose that 4 students play game “2*2=5” vs me – only game nothing else ;) If it is not not “game only” for you, and if you really want to find consensus with me let’s try.
  • One possible way to the consensus is following. Give me a list of your publications about GI. I’ll read them and perhaps it will help me to understand your point of view better. Also, you wrote “It may be possible to find a formulation that we can agree on”. But let you try to edit this my statement as well. Is it possible for you?
  • And again, would you be so kind to restore and keep the statement about regular graphs in the article until the end of this discussion?--Tim32 (talk) 14:56, 14 October 2008 (UTC)
    • Tim32 wrote" "Conclusion. As a rule, regular graphs are difficult for many GI algorithms. Strong regular graphs and some other special cases are exceptions from this rule." - Which is exactly upside down and shows how deeply Tim32 misunderstands the issue. `'Míkka>t 17:30, 14 October 2008 (UTC)
  • Dcoetzee wrote: "it is perfectly acceptable to use original research in arguing on a discussion page". Very interesting idea! Is it your original idea, or can you cite an exact place from wiki rules here? For example, I have polinomial GI algorithm (in printing now). May I describe this algorithm here? And if you or somebody else here will not find any error in this algorithm, then you will delete following statement from the article "Besides its practical importance, the graph isomorphism problem is a curiosity in computational complexity theory as it is one of a very small number of problems belonging to NP neither known to be solvable in polynomial time nor NP-complete." ;-)--Tim32 (talk) 15:18, 14 October 2008 (UTC)
    • The key part is "in arguing on a discussion page". The purpose of article talk pages is to work on article content. How your unpublished paper will help the article content, which must be based on published reliable sources? `'Míkka>t 17:30, 14 October 2008 (UTC)
  • PS. Jitse Niesen wrote: "At the moment, Mikkalai, Arthur Rubin, Dcoetzee and myself are against the sentence that you want to add and only you support it." It is not correct, I do not want to add, it was added! I want to restore only! (See the history page!)--Tim32 (talk) 15:54, 14 October 2008 (UTC)


The above detailed description of table 1,2,3,4 and query servers and stuff demonstrates only that algorithms by Trofimov &Co show no significant degeneration for regular graphs (11 iterations instead of 6, no biggie). Good for them, but this does not address my concern: which reputable sources present a solid argument that regular graphs are "very difficult"? `'Míkka>t 17:33, 14 October 2008 (UTC)

Dear Míkka may I correct you a bit?: but this does not address my concern: which reputable sources for Míkka present a solid argument that regular graphs are "very difficult"? Because sources from Springer-Verlag are not reputable for Míkka :)))))))))))--Tim32 (talk) 18:38, 14 October 2008 (UTC)
PS. Is Springer-Verlag reputable for other persons agreed with Míkka: Arthur Rubin, Dcoetzee, Jitse Niesen? --Tim32 (talk) 18:38, 14 October 2008 (UTC)
PPS. You did not answer my question: Have you any publication? I think this means that you have no.--Tim32 (talk) 18:45, 14 October 2008 (UTC)
Springer is generally reputable, but when an article on a mathematical concept appears in an applied chemistry journal, it's not at all clear the correct review is done. I could give a number of misplaced papers in peer-reviewed journals which are totally bogus, because the reviewers were unaware of the correct references. I have trouble reading Mikka's English, but I have no doubt that Tim's statements are incorrect.
I suppose I could ask my sister (Ph.D. in chemistry, with a thesis in computational protein modelling) whether there's any validity to it. — Arthur Rubin (talk) 18:52, 14 October 2008 (UTC)
Arthur, now it is my turn: I have trouble in reading your English :-) Why would you ask a PhD chemist about an inherently graph theoretical issue? I have no reasons to doubt (and don't care) that Trofimov's GI algorithm works exceptionally well in chemical databases (after all, no one knows why simplex algorithm is so good in practice). I am questioning a rather general general-purpose graph-theoretical statement which goes beyond chemical applications. `'Míkka>t 19:11, 14 October 2008 (UTC)
I think we can use the statements from the article if Trofimov were recognized as an expert in graph theory, or if the paper were published in a graph theory or "theory of computations" journal. I don't think either of those is the case. As for my sister, the questions would be:
  1. Is it a computational chemistry journal, or an applied mathematics journal. If the latter, it would weigh toward inclusion, and I would exppect my sister to be able to determine the difference. I probably could not.
  2. Is Trofimov considered an expert in graph theory or in theory of computations? (Almost certainly not.)
  3. Are the results accepted by graph theory experts. (If so, we should use articles about that acceptance to support the statement, rather than a somewhat questionable journal.)
— Arthur Rubin (talk) 23:21, 14 October 2008 (UTC)

Arthur Rubin wrote: “but when an article on a mathematical concept appears in an applied chemistry journal, it's not at all clear the correct review is done”

Absurd reason: 1) again, we are talking about "Applications" section. I.e. about chemical applications.

2) you did not answer my question: Can you find many sources about chemical applications in pure mathematical journals? For example, in J. of Graph Theory?

3) again, the info from chemical journal is more important for chemical GI applications (adapted for chemistry) than similar info from pure mathematical journal (not adapted for chemistry).

Arthur Rubin wrote:“Is Trofimov considered an expert in graph theory or in theory of computations? (Almost certainly not.) “

Why? You have not any printed articles about GI problem as well as about Mathematical (Computer) chemistry, about computer sci. etc. This means your sci. level is zero. I have printed about 100 articles about noted areas, and there are a lot of links in English Wiki and in Russian Wiki to my articles. This means I can be an expert, you can not!

Arthur Rubin wrote:“I suppose I could ask my sister (Ph.D. in chemistry, with a thesis in computational protein modelling)”

1) How many printed articles has your sister? Please, give me a link to any article.

2) You suggest to ask you sister only, but I already asked the best specialists about – see list in my article.

Arthur Rubin wrote:“I have trouble reading Mikka's English” and Míkka wrote to Arthur Rubin: “I have trouble in reading your English”

Boys! It seems you have problems to read English – perhaps it explains why you unable to understand articles I noted before!!! You are welcome to speak Russian on my talk page, perhaps it would be better for you…--Tim32 (talk) 16:54, 16 October 2008 (UTC)

The statement "Regular graphs are very difficult for isomorphism testing" is not about chemical applications but about graph theory and complexity theory. The content of the statement does not change because it's in the "Applications" section. -- Jitse Niesen (talk) 17:06, 16 October 2008 (UTC)

You are wrong! (sorry for this word, but somebody here has problem to read English and this word was used in Soviet schools, so it will be understable for other my opponents from xUSSR) The content of the statement does change because it's in the "Applications" section. Again you are wrong, because of "Word play will not help."(Míkka). Also, I do note that you unable to answer my questions in my reply to you! And also, again: would you be so kind to restore and keep the statement about regular graphs in the article until the end of this discussion? --Tim32 (talk) 18:21, 16 October 2008 (UTC)

I did not reply because you did not give any new arguments. Simply saying that I misrepresented the papers is not an argument, it's just a statement without any reasons. And I will not restore the statement, because at this point in the discussion (which is not much of a discussion anyway without arguments) it looks very much like the statement should go. -- Jitse Niesen (talk) 20:31, 16 October 2008 (UTC)
It is false. For example, you wrote "I have no idea what the server model in your paper, that you refer to in reply to me above, has to do with it", I cited this model description, but you wrote: "you did not give any new arguments" - this model is new reason for you, for example. Another examples are possible. But let you reread my reply again... --Tim32 (talk) 23:22, 16 October 2008 (UTC)

PS. For my Russian (xRussian) opponents: well-known Russian writer Oleg Kuvaev wrote about similar situation: "Sobachka layala na diady-fraera"! Again, for example, I can suppose that 4 students play game “2*2=5” vs me...--Tim32 (talk) 18:30, 16 October 2008 (UTC)

Arthur Rubin wrote: "but when an article on a mathematical concept appears in an applied chemistry journal" -- It is false! "The Russian Chemical Bulletin is a mounthly jornal covering practically all areas of fundamental chemical research, published by Kluwer Academic/Plenum Publishers." http://www.russchembull.ru/index.php3?id=2 This mistake of Arthur Rubin is good illustration of his and his company methods to prove that 2*2=5! --Tim32 (talk) 19:16, 16 October 2008 (UTC)

Tim has demonstrated that he is the only one in the world who thinks his papers are appropriate references to this article. He also has made it clear that he doesn't understand English well enough to comment sensibly on my argument. If there are traces of his articles in the article, they're going away. Now. — Arthur Rubin (talk) 20:58, 16 October 2008 (UTC)
Arthur Rubin wrote: "he is the only one in the world who thinks his papers are appropriate references to this article" - Wow! 4 boys who have no printed article are "All the world"! Yes, Arthur Rubin, like you I am not native English speaker, but I think, inspite of I'm native Russian speaker I am not sure that me or somebody else will understand such your arguments in Russian or in another language! Anyhow it is personal attack from you! I see, it is your main reason! Very good sci. discussion! --Tim32 (talk) 22:43, 16 October 2008 (UTC)
I should add that, before, during, and after the Soviet era, Russian journals have a somewhat mixed degree of reliability. See lysenkoism for "during", but it's not just the Soviets. Andrew Odlyzko asked me to verify some obscure Russian papers in combinatorics while I was working at JPL, and I found most of them to be incorrect.— Arthur Rubin (talk) 23:30, 16 October 2008 (UTC)
Is it Rasism? Is it Discrimination of another sort? --Tim32 (talk) 00:06, 17 October 2008 (UTC)
1, No. 2, Yes - against including sources that have not been shown to be reliable in this instance. We are discriminating when it comes to good, reliable, sources, and as scientists we wish to see evidence (sorry if this has been said, I only made it through parts of the above; I couldn't let the racism attack stand though) See WP:RS, and also no personal attacks. Verbal chat 19:38, 17 October 2008 (UTC)
In the result of this discussion now you have only one reason to delete this statement: because the source is Russian sci. journal. It is absurd reason. According to this your reason the link: "Zemlyachenko, V. N.; Korneenko, N. M. and Tyshkevich, R. I. (1985). "Graph isomorphism problem". Journal of Mathematical Sciences 29 (4): pp. 1426–1481. doi:10.1007/BF02104746. (Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR (Records of Seminars of the Leningrad Department of Steklov Institute of Mathematics of the USSR Academy of Sciences), Vol. 118, pp. 83–158, 1982.)" also should be deleted from GI article! BTW, Arthur Rubin noted lysenkoism, but may be somebody here knows about Yuri Gagarin, for example. Was "the first human in space" possible for low level of sci? and for low level of sci. journals?--Tim32 (talk) 12:53, 18 October 2008 (UTC)
Arthur Rubin did not answer my questions. At the same time he set a lot of tags on the statement in the article :"[dubious – discuss][verification needed][unreliable source?]". It looks like very strange method to find consensus! Also, note, Dcoetzee edited this statement before. It seems Arthur Rubin now has to find the consensus with Dcoetzee as well.--Tim32 (talk) 12:52, 19 October 2008 (UTC)
No, I was only cleaning up the statement. I have not read the source and cannot verify that it accurately reflects the source. I did find it to be much narrower than the original statement though, which is good. Dcoetzee 02:03, 20 October 2008 (UTC)
All three tags are still appropriate: the source credibility needs to be verified by someone other than an author of the paper; the source content needs to be verified by someone other than an author of the paper; and the accuracy of the statement is still questionable. — Arthur Rubin (talk) 06:49, 20 October 2008 (UTC)
I'm not going to comment on whether regular graphs are "difficult" or not, but it is clear to me that citing Tim32's paper is inappropriate. It is a clear conflict of interest and the paper doesn't even explain what it means by "difficult" or attribute it to another source. Therefore the citation is not very useful--the only thing it proves is that the authors assert without any evidence that regular graphs are "thought to be the most difficult...". I suggest removing the citation, and the entire sentence unless a reliable source is found that actually explains what is meant by "difficult" and that is free of conflict of interest. --Itub (talk) 12:50, 20 October 2008 (UTC)
Agree with Itub. It should be removed. Verbal chat 13:12, 20 October 2008 (UTC)
I have already explained it on this page. Also, I explained why the statement is important for chemical GI applicatins. Please, read this section carefuly! You entered into the end of this discussion, but you did not read what had been written here earlier.--Tim32 (talk) 15:54, 20 October 2008 (UTC)
I did read the discussion and while I admit that you have made some plausible arguments about regular graphs, the fact remains that this is a conflict of interest, and that no one has been persuaded that your article is appropriate for backing up the statement that you want to add. If it is "widely thought" that regular graphs are difficult, you should not have any trouble coming up with an author other than yourself that says so unambiguously. --Itub (talk) 16:22, 20 October 2008 (UTC)
Again: Zemlyachenko, Korneenko and Tyshkevich wrote: “A number of authors (probably, the first were Corneil and Gotlieb [52]; seethe annotation in [I01]) assert that their algorithms have a polynomial complexity for graphs not containing strongly regular subgraphs." Foggia, Sansone and Vento wrote: “On more regular graphs, i.e. on 2D meshes, VF2 is definitely the best algorithm: in this case the Nauty algorithm is even not able to find a solution for graphs bigger than few dozens of nodes." Trofimov and Smolenskii wrote: “Regular graphs are thought to be the most difficult for many algorithms including the graph isomorphism algorithms. However, our tests revealed no fundamental difficulties for this class of graphs.” (Also see, tables 1,2,3,4 in this paper, and the server model). Trivial theoretical “proof” of this fact (note, a graph may has loops (edge (i,i)): for simple backtracking algorithm, which algorithm tests only vertex pairs with the same degree: if all vertices have different degree, then complexity of this algorithm is n; if all vertices have the same degree (regular graph case), then n!. Also, if k vertices have degree deg(k), and other vertices have degree deg(other), then k!(n-k)!. And also, if k vertices have degree deg(k), m vertices have degree deg(m),…, i vertices have degree deg(i), then k!m!…i!(n-k-m-…-i)!. Because n!> k!(n-k)!>…> k!m!…i!(n-k-m-…-i)!, thus the regular graph case is the most difficult. Conclusion. As a rule, regular graps are difficult for many GI algorithms. Strong regular graphs and some other special cases are exceptions from this rule. This rule has practical (may be only practical not theoretical) importance for GI applications in chemistry. --Tim32 (talk) 16:47, 20 October 2008 (UTC)
I'm not getting involved in what seems to be a dispute here, but WP:RS comes into play. Also, I would suggest that the suggestion all Russian science journals are not reputable because of Lysenkoism not be pursued, because one could easily call all American science journals' reliability into question, as I do believe that homosexuality was officially listed as a curable mental disease by American science journals and medical associations in that country for many decades, and I also believe some 'western' journals believed being non-white was akin to a form of retardation. To call into question sources from one country by citing unrelated subjects is not on, and should be agreed to by editors of articles based upon WP:RS, without idiotic tarring with one brush all sources from one country. --Russavia Dialogue Stalk me 08:12, 26 October 2008 (UTC)

Reference structure

(Almost) all references have a blue-link from the Harvard citation which doesn't in fact, lead anywhere. I don't know if this can be fixed. — Arthur Rubin (talk) 21:34, 12 October 2008 (UTC)

If you're referring to the links in the notes section, those are just section links to the corresponding reference. If your browser already has them in view, it will not scroll to reveal them. Dcoetzee 21:55, 12 October 2008 (UTC)
Sorry. It seems non-standard, but I guess it's OK. — Arthur Rubin (talk) 22:02, 12 October 2008 (UTC)

Class GI

Yesterday I made a quick fix for the "Complexity class GI" section. I removed a reference to an article which was confusing "completeness" and "hardness" in computational complexity. I could have added a ref right off my head, but I would find the one which says who introduced this notion. I can find it myself after some research, but may be someone already knows one? Twri (talk) 18:01, 14 October 2008 (UTC)

Hmm, you're right, I don't know how I overlooked this. :-( To be GI-complete it must of course be both GI-hard and in GI. I think the original description was tacitly assuming the problems under discussion were in GI, but the new text is better. Dcoetzee 00:21, 15 October 2008 (UTC)

Another application, in digital feature film animation

Given all the fuss over some other self-serving edits to this article, I'm certainly not going to add this one to the article myself. But, here's a recent paper of mine which includes a description of another application of graph isomorphism as part of the process for computer animation (as used e.g. at Disney):

The relevant parts are the bullet "mesh isomorphism" in the introduction, and section 6, "Mesh Isomorphism". The graphs to be tested for isomorphism come equipped with an embedding onto a topological surface, making it much easier to test isomorphism for them. The overall paper is about a data compression technique that allows isomorphism testing to be performed even more quickly for this case. Unfortunately I don't know of other work describing this application (if I did I would have cited them). I'll leave it to others to determine whether it's as deserving of a place in the article as the other applications listed; I'm too close to the subject to have a trustworthy opinion myself. —David Eppstein (talk) 05:23, 21 October 2008 (UTC)

I think you can add this to the application section and you should not ask about it here. But there are experts of this talk page who may find conflict of interest and so on. This their absurd position is very distructive for Wiki, and this your situation when you are afraid to do obvious edition yourself is good illustration of that. The most interesting fact is that these experts have not printed articles.--Tim32 (talk) 15:47, 21 October 2008 (UTC)
It looks interesting, I'll have a read when I have time. Tim: Do you realise who you're claiming has no publications?? We don't argue from authority here though - that's not how it works. Please keep on topic in new threads, and stop your attacks and disruption. Verbal chat 16:27, 21 October 2008 (UTC)
There is no attack. However, if you have printed any paper about GI problem or about graph's applications, please, give me a link - perhaps, it will help me to understand your point of view. For example, this paper helps me to understand some passages by David Eppstein. Thanks! --Tim32 (talk) 19:46, 21 October 2008 (UTC)

SMILES deleted ?!

Recently Míkka deleted info about SMILES (simplified molecular input line entry specification) from the application section. Before it "[citation needed]" tag was set on this info. However there was the link to SMILES article in this info, where (in the SMILES article) we can find a lot of references. But these references are references to chemical issues, perhaps, it may explain motivation by Míkka, because Míkka wrote that chemical journals are not reputable for GI article. Anyhow it looks like deletion mania: delete, delete and delete everything. BTW, it is interesting to read Míkka user page -- this time he has a lot of problems for deletions in other pages. I am not specialist from subjects of those pages, but it seems Míkka is specialist in everywhere and he deletes, deletes and deletes everything on all pages. Let it be, but it is very strange for me. Anyhow I see that Míkka makes worse GI article step by step.

A few words about SMILES. It is not very good notation. For example, it has problems for some regular graphs ( cuneane, etc.), but it is widely distributed and so it has to be noted in the application section. --Tim32 (talk) 18:08, 22 October 2008 (UTC)

PS. Note, please, it is only for NPOV -- I myself dislike the SMILES and I did not advise it anywhere in my printed articles.--Tim32 (talk) 18:12, 22 October 2008 (UTC)

Edits by Míkka and Arthur Rubin

Míkka and Arthur Rubin currently restarted an edit war according to the reverts I had made on the Applications section. At the same time they did not answer "SMILES deleted ?!" section on this page. Also they were disagreed that "Regular graphs are very difficult for many GI algorithms", but I proved this statement in this talk page --see, "Regular graphs are very difficult" section. Than Arthur Rubin wrote that all Russian sci journals are not reputable, and Russavia proved that this is false. Arthur Rubin did not answer this remark by Russavia also. In new edition I did not use the word "difficult" that word so disliked by Míkka and Arthur Rubin. However they repeatedly revert edits, and they do not use the talk page for a consensus among editors.--Tim32 (talk) 01:22, 13 November 2008 (UTC)

PS. BTW, I wrote here to Verbal "if you have printed any paper about GI problem or about graph's applications, please, give me a link - perhaps, it will help me to understand your point of view." He did not answer me as well.--Tim32 (talk) 01:27, 13 November 2008 (UTC)

Nonsense again. I didn't write that all Russian science journals are not reputable; but a number of them during the Soviet era were, and not for political reasons, so there's no reason to assume that they are now reputable. Furthermore, even if your article is reliable, you never supported the statement that "regular graphs are difficult", but only that certain algorithms don't work well on regular graphs. (It would be WP:OR to state that those algorithms are commonly used, even if it were correct.)
As for consensus; there is a consensus of all but you that the "regular graph" statement is not adequately supported.
There seems to be a consensus of all but Mikka that most of his material isn't supported, either....
— Arthur Rubin (talk) 02:19, 13 November 2008 (UTC)
About Mikka: what "his material" you are talking about? I am not pushing my own mathematical exercises into wikipedia articles. If you question any statements I am adding to wikipedia, you know better what to do. `'Míkka>t 15:39, 13 November 2008 (UTC)
"Using material you yourself have written or published is allowed" (WP:COI)--Tim32 (talk) 16:38, 13 November 2008 (UTC)
Nice cutting half-sentence out of context, thank you. `'Míkka>t 18:57, 13 November 2008 (UTC)
Do you want to say that Using material you yourself have written or published is forbidden?--Tim32 (talk) 19:36, 13 November 2008 (UTC)
From WP:COI (emphasis added): "Using material you yourself have written or published is allowed within reason, but only if it is notable and conforms to the content policies. Excessive self-citation is strongly discouraged. When in doubt, defer to the community's opinion." OK, I know you are not in doubt, but the community's opinion (i.e., anyone who has commented here other than yourself) is that the reference to your work is not appropriate. --Itub (talk) 20:46, 13 November 2008 (UTC)
I have replied on Tim's talk page, as his comments have nothing to do with improving the article. Verbal chat 08:38, 13 November 2008 (UTC)
It is false! For example, see history of this page: I had noted here: "I can not find the word "automorphism" in this article", after that the article was improved and "automorphism" was added etc.--Tim32 (talk) 15:58, 13 November 2008 (UTC)

And why SMILES had been deleted ?! Was it "improving the article"?--Tim32 (talk) 14:22, 13 November 2008 (UTC)

Because it was in dubious context. There is no proof presented that usage of SMILES in cases where they work well, i.e., for simple structures, is faster than some trivial graph isomorphism algorithm. `'Míkka>t 15:33, 13 November 2008 (UTC)
The SMILES is widely distributed and so it has to be noted in the application section! --Tim32 (talk) 15:49, 13 November 2008 (UTC)
The "applications" section is for application of graph isomorphism algorithms. SMILES is application of SMILES or whatever it is based upon. `'Míkka>t 18:57, 13 November 2008 (UTC)
SMILES is based on GI problem. --Tim32 (talk) 19:41, 13 November 2008 (UTC)
SMILES is not based on the GI problem. Maybe you could say that canonical SMILES is, but that's another story. It doesn't have any "difficulties" with benzene or cyclohexane anyway; what algorithm would have "difficulties" with such small graphs? And the fact that there are a handful of important chemicals with regular graphs (out of tens of millions of known chemicals) hardly implies that "regular graphs are important for chemistry" (and even if they were, that would be a bit off-topic for this article). --Itub (talk) 20:46, 13 November 2008 (UTC)
Again I wrote SMILES has problem for cuneane. It is GI problem. SMILES is the type of canonical numeration, this canonical numeration problem is linked with GI problem. --Tim32 (talk) 21:14, 13 November 2008 (UTC)
Itub, you beat me to a minute. I intended to write the following comment "Tim32, if you say so (which is false, BTW), then the phrase in question is plainly meaningless." I was sitting on my hands not writing a series of articles in computational complexity and graph isomorphism, waiting for this piece of Tim32's ignorance in graph isomorphism theory to pop out in this talk page as a final confirmation that the discussion with him is useless. Now you may read and write about SMILES and GI and why there are so many claims for "very efficient" GI algorithms here. Frankly, I am quite surprized that this article was missing until now. `'Míkka>t 20:54, 13 November 2008 (UTC)
You wrote that discussion with me is useless, however when I added an info about Hosoya index, you used this info just the moment ;-) --Tim32 (talk) 21:14, 13 November 2008 (UTC)
I used it because it was useful, relevant and verifiable info, and I didn't have to argue with you. I am not saying that you know nothing. I am saying that you have a rather limited understanding of the graph isomorphism problem and refusing to accept this. `'Míkka>t 23:20, 13 November 2008 (UTC)
About "rather limited understanding of the graph isomorphism problem": Please see Wikipedia's no personal attacks policy. Comment on content, not on contributors.--Tim32 (talk) 01:55, 16 November 2008 (UTC)

To Arthur Rubin: you wrote: "before, during, and after the Soviet era"! Also if "certain algorithms don't work well on regular graphs" then regular graphs are difficult for some GI algorithms. --Tim32 (talk) 14:22, 13 November 2008 (UTC)

Some algorithms don't work on non-bipartate graphs. Does that make non-bipartate graphs "difficult". — Arthur Rubin (talk) 14:37, 13 November 2008 (UTC)
Yes it does, non-bipartate graphs are difficult for these algorithms. But in my revised edition I wrote "regular graphs are very important for chemistry". (there was not "difficult" in this my edition) Have you some reason against? And again, why you deleted the info about SMILES?--Tim32 (talk) 15:18, 13 November 2008 (UTC)
"Very important" is a dubious unreferenced statement. The correct statement is "regular graphs are used in chemistry" (along with numerous other types of graphs). `'Míkka>t 15:30, 13 November 2008 (UTC)
See refs to very important regular graphs in chemistry: cyclohexane, benzene, cuneane, dodecahedrane... Would you like more? --Tim32 (talk) 15:37, 13 November 2008 (UTC)
Quite. There is no evidence presented that the regular graphs of those substances are more important than non-regular graphs of other substances. Even if it were important, it shouldn't be in this article, but in a different graph theory article or a chemistry article. — Arthur Rubin (talk) 18:14, 13 November 2008 (UTC)
The word "important" is often abused to the degree of truism. Wikipedia has a policy "avoid peacock term" for a reason. The unbeatable (although unreferenced) logic of Tim32 sound like this: "fricative consonants are very important in mathematics. They are widely used, e.g., in the famous Euclid's fifth postulate". In fact they are indispensable in 95% of proofs of mathematical theorems, and for the remaining 5% great efforts are required to restate them without fricative consonants, while producing correct but highly incomprehensible texts." (OK, OK, I admit the last sentence is my unpublished OR, but the rest is solid and easily verifiable truth: just read theEuclid's fifth postulate and see it for yourselves.) `'Míkka>t 18:57, 13 November 2008 (UTC)
It is word play only. This is page to talk about GI article, not about Euclid's fifth postulate. Ask any chemist about importance of cyclohexane and benzene. Read any chemical textbook to understand it. It is obviously for chemists, but you are poor informed in chemical area and in GI applications for this area. It is well-known that to test any program you need to make the test set for the most important objects, read article by W.C.Herndon in the book "Chemical Applications of Topology and Graph Theory", ed. by R. B. King, Elsevier, 1983 about regular graph in chemistry and about their difficulties for GI and for SMILES-like notations.--Tim32 (talk) 20:07, 13 November 2008 (UTC)
PS. M.I.Nechepurenko, V.K.Popkov and others noted regular graph importance and difficulty for GI apllications in their book "Algorithmy i programmy reshenia zadach na grafax i setiax", Novosibirsk: Nayka, 1990, S.21 -- you speak Russian, so it is not a problem for you to read this.--Tim32 (talk) 20:20, 13 November 2008 (UTC)
It was a reasonable analogy. I think you're not going to convince us on this, but if you feel strongly I'd advise you to start an RfC about whether your phrase and reference should be included - I think I advised this before. I think that's the only possible way you might establish consensus in favour of your edits. Verbal chat 20:31, 13 November 2008 (UTC)
Maybe, but it would be necessary firstly to understand the subject. Let you formulate it: "SMILES and GI", "regular graph importance for chemistry","importance of cyclohexane and benzene", "regular graphs are difficult for chemical applications", "regular graphs part among chemical compounds is small, and decreases with increasing of number of vertices", "all Russian science journals are not reputable", "Tim32 is pushing his own mathematical exercises into wikipedia articles","Who the heck is this Trofimov? What's his international scientific recognition?", "Using material you yourself have written or published is forbidden", "assertion "graphs, in chemistry, have degree at most 8" is false", "the algorithm by Luks (for graphs of bounded degree) is not adopted for chemical compounds", "to test any program you need to make the test set for the most important objects" or something else?--Tim32 (talk) 20:54, 13 November 2008 (UTC)
PS. Any reasonable analogy is not proof.--Tim32 (talk) 20:59, 13 November 2008 (UTC)
We've tried to be reasonable with you, but now I'm going to WP:SHUN your posts here on this and related topics until you either accept consensus or file an RfC. I invite others to do the same. (If other editors feel this isn't a good idea, let me know below) Verbal chat 21:11, 13 November 2008 (UTC)
I tried to be reasonable with you, as well, but you did not answer my questions. About the subject, about help, about SMILES etc. Why you are so agressive?--Tim32 (talk) 21:26, 13 November 2008 (UTC)

Incorrect statemnt

"Since the molecular graphs have bounded degree (as the valence of any atom is at most 8), their isomorphism is testable in polynomial time[26]."

1)"as the valence of any atom is at most 8" -- Valence (chemistry) is very complicated conception and it is not the same as vertex degree, for example, see Ferrocene -- vertex degree is 10 (for Fe). Also for some approaches, for example, for chemical reactions database the vertex degree may be >>10. See, the article by C.S. Wilcox, R.A. Levinson, ASC Symposium Series 306, Artificial Intelligence Applications in Chemistry, Ed. T.H. Pierce, American Chemical Soc., DC, 1986.

2)the algorithm by Luks [26] (for graphs of bounded degree) is not adopted for chemical compounds, for example, what about molecular with double bonds?

Note, I did not say that it is not possible to use the algorithm by Luks for chemical tasks, but its adoptation would be an original research.--Tim32 (talk) 16:09, 16 November 2008 (UTC)

Perhaps. But the statement is certainly more likely than the unsourced "regular graphs of interest to chemists are difficult". Perhaps the entire section on chemistry should be be removed. — Arthur Rubin (talk) 16:19, 16 November 2008 (UTC)
I'm on Tim's side in this one, this claim is suspect. We really need to figure out something definitive and well-sourced we can say about chemical structural applications. Dcoetzee 16:25, 16 November 2008 (UTC)
Ok! Thanks for fast solution. According to "regular graphs of interest to chemists are difficult" I already noted an additional links:
1) The article by W.C.Herndon in the book "Chemical Applications of Topology and Graph Theory", ed. by R. B. King, Elsevier, 1983.
2) M.I.Nechepurenko, V.K.Popkov and others, Algorithms and program's solutions of tasks for graphs and nets. (in Russian: Algorithmy i programmy reshenia zadach na grafax i setiax), Novosibirsk: Nayka, 1990, S.21.
You did not answer it!
According to "Perhaps the entire section on chemistry should be be removed" - it would be very strange! Any application area is very important for mathematical tasks! We have a lot of beautiful tasks, which marked as practically useless, because they have no applications. So, I also supported the idea by User:David Eppstein to add link to his article to the GI Applications section. Unfortunately, nobody else supported this his idea. --Tim32 (talk) 16:56, 16 November 2008 (UTC)
Perhaps the entire section on chemistry should be removed, unless the section is rewritten so as not to imply that the chemists are using the best mathematical techniques. (I am an expert in complexity theory, and in some aspects of graph theory. Grumble.) Tim may be an expert in the techniques and graphs used by chemists (or, at least, Russian chemists), but claiming that the problem is mathematically difficult for regular graphs is {{dubious}}.
Unfortunately, combining the claim that most graphs of interest to chemists are planar and that the isomorphism question for planar graphs can be solved in polynomial time may also be WP:SYNthesis. — Arthur Rubin (talk) 19:54, 16 November 2008 (UTC)
Putting two sentences side by side with no conclusion made, is hardly synthesis. However I highly doubt that palanr graphs isomorphism is used by chemists hence the planagity issue is irrelevant to "chemical applications" part, unless referenced. `'Míkka>t 01:41, 17 November 2008 (UTC)
Perhaps the statement on difficulty should be "regular graphs of interest to chemists are difficult for chemists"? — Arthur Rubin (talk) 19:55, 16 November 2008 (UTC)
As for ferrocene, even our articles notes that the the two-atom bond model fails, making the problem of assigning a graph to the compound "difficult". — Arthur Rubin (talk) 19:59, 16 November 2008 (UTC)
  • You wrote: "I am an expert in complexity theory, and in some aspects of graph theory." -- Why do you think so? Can you prove it? Also, acording to your talk page and your contributions page I see that you are expert in many different areas: in "Electron structure of the Atoms" and in "Training (meteorology)" and in "Child sexual abuse" and in "Day care sex abuse hysteria" and in "8th millennium" and in many others. Is it possibble to be an expert in such different areas?
  • You wrote: "at least, Russian chemists" -- did you want to say that American chemists are better than Russian chemists?
  • You wrote: "mathematically difficult for regular graphs" -- I did not use "mathematically difficult", only "difficult": do you see the difference? the difference for applications??
  • Moreover, you wrote: "mathematically difficult for regular graphs is {{dubious}}", but at the same time you did not answer my question about the article by W.C.Herndon in the book "Chemical Applications of Topology and Graph Theory", ed. by R. B. King, Elsevier, 1983, and about M.I.Nechepurenko, V.K.Popkov and others, Algorithms and program's solutions of tasks for graphs and nets. (in Russian: Algorithmy i programmy reshenia zadach na grafax i setiax), Novosibirsk: Nayka, 1990, p 21. Formally only, you can write that the book edited by R. B. King is chemical book, but the book by Nechepurenko is not chemical book only!
  • As it was asked for some othe case above, please explain what arguments and references are used by both Herndon and Nechepurenko in support of the statement in question that "regular graps are difficult" and how exactly they phrase this statement. `'Míkka>t 01:41, 17 November 2008 (UTC)
  • Nechepurenko: "Особое внимание заслуживают сильнорегулярные графы. [...далее следует определение сильнорегулярного графа - tim32] Из [67] известно, что сильнорегулярные графы образуют класс наиболее трудных для распознавания изоморфизма графов и большинство контрпримеров для эвристических алгоритмов РИГ входит в указанный класс. Для сильнорегулярных графов относительно быстрый алгоритм с числом действий O(exp(2sqrt(p)log2(p))) построен в [68]." М.И.Нечепуренко, В.К.Попков и др. Алгоритмы и программы решения задач на графах и сетях. Новосибирск: Наука. 1990. стр. 21-22. Where: [67]: В.Л.Арлазаров, А.А.Леман, М.З.Розенфельд, Построение и исследование на ЭВМ графов с 25, 26 и 29 вершинами. М.: ИАН АН СССР, 1975. 58 с. [68]: L. Babai, Isomorphism testing and symmetry of graphs. Annals of Discrete Math., 1980, vol. 8, p. 101-109.--Tim32 (talk) 18:56, 18 November 2008 (UTC)
"Let G = (V,E) be a regular graph with v vertices and degree k. G is said to be strongly regular if there are also integers λ and μ such that: Every two adjacent vertices have λ common neighbours. Every two non-adjacent vertices have μ common neighbours." (strongly regular graph) So, regular graph is a type of a graph, strongly regular graph is sub-type of regular graph. --Tim32 (talk) 17:12, 19 November 2008 (UTC)


  • Herndon wrote big article, the main part of this article about problems for regular graps, I hope you are able to find this book and to read the article yourself. This is very good article, and I think you will have no problem to understand it, so I see no reason to explain arguments by Herndon here. If you will have any question after reading, please, let me know, I will try to explain. But, note, it is not my approach, it is approach by Herndon.--Tim32 (talk) 18:56, 18 November 2008 (UTC)
  • No this book in my close libraries. However from what Herndon wrote elsewhere I doubt that he claimed that regular graphs are difficult. In some other places he wrote about "highly symmetric" regular graphs, which of course makes sense. `'Míkka>t 20:17, 18 November 2008 (UTC)
If you want we can write: "some types of regular graphs are difficult". Are you agreed? --Tim32 (talk) 17:12, 19 November 2008 (UTC)


  • To respond to some of your attacks:
  1. I am not an expert in all those fields. There is no restriction against amateurs editing. However, I am an expert in complexity theory (2 published papers, at a non-academic employer) and graph theory (1 published paper, credits in some of Erdos's work).
  2. I think I'll defer to your answer to Mikka's question before I deal with the "difficult" part, as no quotes which indicate that a reliable sources reports that the graph isomorphism problem is difficult on regular graphs.
  3. And ferrocene does not have traditional 2-atom molecular bonds, so the question of what graph should be used is interesting. — Arthur Rubin (talk) 14:00, 17 November 2008 (UTC)
  • Yes, the ferrocene has non-standard bonds, but note, please, there are many types of chemical bonds: Strong chemical bonds, Covalent bond and Polar covalent bond, Ionic bond, Bent bonds etc and the bond in chemical molecule and an edge in molecular graph are different things. The molecular graph is model only, very often we do not distinguish bond types for the graph's edges. So, for many applications the vertex "Fe" in molecular graph of ferrocene may have degree 10.--Tim32 (talk) 18:56, 18 November 2008 (UTC)
  • You wrote: "To respond to some of your attacks" -- there were no attacks from my side, I only tried to understand your point of view. Also you wrote "I am an expert in complexity theory (2 published papers, at a non-academic employer) and graph theory (1 published paper, credits in some of Erdos's work)." Ok! It is sufficiently for my understanding why you think that you are expert in noted areas. I printed more papers (for example in J Math Chem, in Byte (magazine), in First Class by OMG, etc.), also I took part in Extended Pascal and in Dr. Pascal projects by Visible Software (US) and many of students in the world studied programming via these tools, so perhaps, I also can say "I'm expert"... Thanks. Anyhow, again: if possible, please, give me links to your publications - perhaps, it will help me to understand your point of view. For example, the paper by David Eppstein noted here helped me to understand some his passages.--Tim32 (talk) 18:56, 18 November 2008 (UTC)
  • I strongly suggest you both to stop this pissing contest. OK Tim, we can agree you are an expert. An expert who does not know the difference between strongly regular and regular graphs. Your words speak much more about your expertise than your credentials. It is amazing that you seem fail to understand that your bragging actually hurts you. After what you uttered here many times, your statement that "many of students in the world studied programming via these tools" makes me feel sorry for them rather than respect you. `'Míkka>t 20:17, 18 November 2008 (UTC)
  • As you could see, I do know the difference between strongly regular and regular graphs. Again strongly regular graph is sub-type of regular graph. This your agressive message looks like WP:ATTACK only.--Tim32 (talk) 17:28, 19 November 2008 (UTC)
  • (ec x2) Well, the Erdos paper in Arthur Rubin is in graph theory, and one of my related results (of which I don't recall whether it's in that paper) is that "3-choosability" is -complete in the sense of the polynomial hierarchy. Most of my other works in graph theory and complexity theory are unpublished, or to note that some of the reductions in my parents' books Equivalents of the Axiom of Choice are actually polynomial-time reductions, even if the underlying problems of finding a choice function are NP-complete. I believe I'm credited with a proof in 2 others of Erdos's graph theory papers where I wasn't considered a co-author. — Arthur Rubin (talk) 21:44, 18 November 2008 (UTC)
  • Thanks! Your article "Kinna-Wagner selection principles, axioms of choice and multiple choice". 1) It was printed by Springer like my paper. Why did you say that my article (=your article) publisher is not reputable? 2) You "study the relationships"... Do you see relationships between strongly regular and regular graphs? Do you see that regular graph is a type of a graph and strongly regular graph is sub-type of regular graph? Also your article "Digital SAR processing using a fast polynomial transform" looks like application, yes? In this case you have to understand the difference between practicy and theory. Do you understand this difference? I also noted that the article about you was nominated for deletion on 30 July 2008 and on September 20, 2006, but I have no comments about. I also noted that you was born in 1956, me is born in 1957. I surprised that for this long time period you had printed a few articles only, but it is your business, sorry!--Tim32 (talk) 20:49, 19 November 2008 (UTC)
  • PS. You did not answer my question: you wrote: "at least, Russian chemists" -- did you want to say that American chemists are better than Russian chemists? --Tim32 (talk) 20:50, 19 November 2008 (UTC)
  • Unlike certain notable Wikipedia editors, I considered it improper to add my publication list to the article. Perhaps I'll add it to my user talk page. And I'm a non-academic mathematician, so my employer doesn't encourage publication. (Apparently, it's also improper for me to comment on the AfD of my article, which I discovered after the first deletion proposal. My only edit to Arthur Rubin, other than reverting clear vandalism, is adding my date of birth; under WP:BLP, the persons concent is required for a non-public figure.)
  • I recall some Springer imprints as being not-very-well reviewed, or possibly not peer-reviewed at all. I haven't checked the reputation of your specific imprint.
  • Yes I do understand the difference between practice and theory. I still don't see why the reviewers for a computational chemistry journal may be up on the best mathematical practices, even if the paper is well-reviewed.
  • I don't know that American chemists even write about the chemical isomorphism problem, which may only loosely be related to the graph isomorphism problem.
  • — Arthur Rubin (talk) 23:45, 19 November 2008 (UTC)
Okay, I think what we really want to do here is: describe the graph isomorphism algorithms used by chemists and the manner in which they use them. We shouldn't synthesize work from graph theory and computer science with work from chemistry on our own; nor should we discuss the undocumented practical difficulties encountered by chemists with their systems. Let's start out by just describing what they use. Dcoetzee 21:24, 18 November 2008 (UTC)
In other words, develop the coverage of Chemical graph theory (mathematical chemistry) in wikipedia bottom-up. It is always a good idea, but seldom works systematically unless you have a strong team to start a wikiproject. From my brief encounter with the topic I have a strong impression that 80% of their research is magical voodoo as in "Voodoo programming". A good deal of the papers in molecular identification write something like this. "Balaban index J has very strong discrimination power. If we then apply the eigenvalue criterion, the graphs most certainly will be nonisomorphic. I know the smallest pair of graphs not discriminated in this way is on 40 vertices, but they are not chemical graphs. I wrote a program which counts all nonisomorphic subgraphs of molecular graphs up to 100 vertices and it made a counting error of 1 in 3 cases only. But in these cases these graphs are discriminated by the M-W index. This was implemented in my program FICS-22 (Fast Identification of Chemical Structures). No counterexamples have been found so far." And the real beauty is that all these algorithms indeed run great! I know colleague Tim32 can tell you much more about various topological indices. `'Míkka>t 22:08, 18 November 2008 (UTC)
P.S. Another weird thing is that chemical graph theory is not part of computational chemistry, some say. Not forgetting about a new coinage of cheminformatics. In other words, from wikipedia is impossible to figure out which of these crossover sciences the chemical graph isomprphism belongs to. `'Míkka>t 22:08, 18 November 2008 (UTC)
  • Can you prove that GI algorithm described in M.I.Trofimov, E.A.Smolenskii, Russian Chemical Bulletin, 2005, Vol. 54, 9, 2235 is not correct? Do you find any error?
  • Your example, about topological indices usage for GI testing: it is well known that for every index there are nonisomorphic graphs with the same index, and nobody found sum of any indices, which sum may be used to test GI without error. But topological indices usage is very useful for GI testing for fast pre-test. It seems you are poor informed in area of practical programming. You discussed every task under abstract mathematical view only, but you do not imagine practical way to solve real GI task for real system. Do you understand that very often strong abstract matematical approach is not a way for applications? According to your point of view not only programming in chemistry but almost all physical models are "Voodoo programming"! It means that you are poor informed in metodology of modern experimental science also.--Tim32 (talk) 18:14, 19 November 2008 (UTC)
Let's not get involved in a methodological debate here - it's clear that computational chemistry applications use different algorithms designed in a different way, and it's not Wikipedia's mission to reform research practice. The question is what article or articles this should be described in, and how to sum up how graph isomorphism is solved in practical chemistry applications. Dcoetzee 20:28, 19 November 2008 (UTC)
I thought I summarized it quite well and colleague Tim32 confirmed it (although he thinks he rebutted me): it works because they run it and it works (and I recently added a ref with some explanation: because even the simplest tricks work well almost always for GI). And this approach is called voodoo programming. In 20 min of googling I can find you about 200 different graph somorphism algoriths, all of them are ranging from "very good" to "fastest" by their authors. To Tim32: Yes. I know the difference between mathematical and engineering approaches. I also know a big number of jokes on this issue. Now, jokes aside, from wikipedia point of view any algorithm or piece of software must meet at least one of basic criteria of notability and verifiability to be included here:
  • It must be reviewed by a respectable source/author from the industry in question to confirm that the algorithm has distinctive features (novelty, speed, accuracy, etc.) worth of note.
  • It must be part of a commercially successful product
  • It must be of recognized standard/preferred usage by a notable academic/scholar/governmental organization, confirmed by sources independent of the author.
The above criteria are common sense right out of my head. Possibly others may add more. Furthermore, not every mentioning in a review is a carte blanche to write a 60Kb description in wikipedia. For example, if peer reviews only say that the algorithm is worse than others, then it hardly deserves to be here. See WP:NOTE & WP:PRODUCT Now, what you may say about the notability of Trofimov&Smolenskii's algorithm besides what is written in authors' own articles? `'Míkka>t 00:30, 20 November 2008 (UTC)
  • I think the main part of 200 GI algorithms you found are heuristic algorithms. In contrast with Trofimov&Smolenskii's algorithm, which correctness had been strongly proven. Scientific algorithm must not be a part of a commercially successful product and many well-known good algorithms are not standard for any organization. Standard algorithm for scientific research looks like nonsence! I am agreed with Dcoetzee: "it's not Wikipedia's mission to reform research practice". Also, note Wikipedia:Core content policies: "Verifiability – Material challenged or likely to be challenged, and all quotations, must be attributed to a reliable, published source. The threshold for inclusion in Wikipedia is verifiability, not truth—meaning, in this context, whether readers are able to check that material added to Wikipedia has already been published by a reliable source, not whether we think it is true." But in this discussion you try to solve "is it true?" A fact or idea which was published in international peer-reviewed journal may be inserted into Wiki article as is. Wiki editors are not official experts to solve "is it true or not?" For example, I noted on this page, I dislike SMILES (and know SMILES errors), but I was disagreed with its removing, because of WP:NPOV.--Tim32 (talk) 15:12, 21 November 2008 (UTC)
  • "this approach is called voodoo programming" -- it is not true: so-called "voodoo programming" is defined as coding, do you know differences for algorithm and its realization? differences for algorithm description and listing? Also, "voodoo programming" is not approach...--Tim32 (talk) 15:12, 21 November 2008 (UTC)
  • Definitions: "In graph theory, a regular graph is a graph where each vertex has the same number of neighbors, i.e. every vertex has the same degree or valency." (Regular graph ) "Let G = (V,E) be a regular graph with v vertices and degree k. G is said to be strongly regular if there are also integers λ and μ such that: Every two adjacent vertices have λ common neighbours. Every two non-adjacent vertices have μ common neighbours." (Strongly regular graph) So, regular graphs are sub-set of set of all graphs, strongly regular graphs are sub-set of set of regular graphs. We can write "some types of regular graphs are difficult for many practical GI applications". Are you agreed?--Tim32 (talk) 15:12, 21 November 2008 (UTC)
  • Again, see the article by W.C.Herndon in the book "Chemical Applications of Topology and Graph Theory", ed. by R. B. King, Elsevier, 1983 and cited book by M.I.Nechepurenko.--Tim32 (talk) 20:03, 21 November 2008 (UTC)
Regarding "A fact or idea which was published in international peer-reviewed journal may be inserted into Wiki article as is." Yes, if the consensus is that the fact or idea is notable and relevant to the article. In addition to the verifiability policy that you mention, there are also rules about notability and about undue weight. When the only person who thinks that an article needs to be cited is the author of the article, who appears to be interesting in promoting his own work by adding self-citations in multiple places in Wikipedia, that's not a good sign. According to Web of Science, no one has cited your paper yet in the three years since its publication. Why should Wikipedia cite it then? --Itub (talk) 16:14, 21 November 2008 (UTC)
See this page: "arXiv.org also contains an earlier paper "A Polynomial Time Algorithm for Graph Isomorphism" by Reiner Czerwinski, arXiv:0711.2010v3. Unlike Friedland, Czerwinski has no refereed publications in mathematical journals so far. (Or possibly one?) Czerwinski quotes a 2005 paper by Trofimov and Smolenskii in the "Russian Chemical Bulletin" (sic), and claims that already that article contained a "program for graph isomorphism with polynomial run time".Aleph4 (talk) 10:09, 8 January 2008 (UTC)" -- The arXiv:0711.2010v3 is preprint only, but lets wait -- publications such important statements as "program for graph isomorphism with polynomial run time" is very long process. Otherwise, only obsolete articles may be used for Wiki. Anyhow again there are not official experts in Wiki to solve "is it true?" problem!--Tim32 (talk) 19:48, 21 November 2008 (UTC)
Actually, no. We can't use ArXiv publications as references (as they're essentially self-published with only typographical review), and there are not official experts in Wiki to solve "is it true?" problems. In most cases, Wikipedia editors accept the consenus of the relevant experts who happen to be Wikipedia editors, but that appears not to be the case here. — Arthur Rubin (talk) 22:46, 21 November 2008 (UTC)
I would state it as "We can't use ArXiv as references in controversial cases". Our policy on self-published sources does allow them to be used when they're by established experts, but only with care. ArXiv should count as a self-published source because the level of review a paper undergoes to be accepted there is very minimal (essentially, a moderator checks that it is on-topic, but not whether it is correct or whether it makes a novel and useful contribution to the subject). —David Eppstein (talk) 22:51, 21 November 2008 (UTC)
Quite correct, sorry. — Arthur Rubin (talk) 23:13, 21 November 2008 (UTC)

Again, you did not answer my questions. Herndon, Nechepurenko, Popkov, Zemlyachenko, Korneenko, Tyshkevich, Foggia, Sansone, Vento, Trofimov, Smolenskii wrote that some types of regular graphs are difficult for number of practical GI applications. Note, according to definitions the regular graphs are sub-set of set of all graphs, strongly regular graphs are sub-set of set of regular graphs. Only graph canonization approach was noted for chemical applications. It is incomplete. We found that there are not official experts in Wiki to solve "is it true?" problems, so we should not try to solve "is it true?" for any of noted articles as well as for methodology of GI applications testing! The fact is that not only canonization approach and heuristic algorithms are used for chemical GI applications, but also strong proved approach by Trofimov and Smolenskii. Another fact is that some types of regular graphs have to be used for testing ( for benchmark (computing) tests also!). --Tim32 (talk) 13:27, 24 November 2008 (UTC)

I am afraid that the phrase "some types of regular graphs are difficult" is misleading, since it puts undue weight on coincidental fact of difficult graphs being regular. Just the same, it may be said that "some graphs with more than 500 vertices are difficult for graph isomorphism". First, there is no evidence that the fact for graph being regular creates insurpassable difficulty. Second, regular mesh graphs are not regular graphs, yet they deliver difficulty for many graph isomorphism problem. From the point of view of common sense, it is not surprizing that the amount of regularity in a graph may lead to difficulty for GI algorithms, especially those based on vertex classification approach. However a mere vertex regularity is far cry from being a stumbling stone: after the first step of vertex classification based on vertex degree this "first-level regularity" is effectively peeled off and plays no further role and being quite fast gives no serious deterioration of computational complexity. Exactly for this reason the classes of strongly regular graphs and distance regular graphs were considered. They were constructed specifically as counter-examples for certain approaches to refinement procedures in vertex classification approach, the first one based on the extention of the notion of regularity for neighborhoods for vertex sets (the ordinary regularity is the case of single-element vertex sets) and another one is the refinement based on the numbers of vertices at distance d from a given vertex (vertex classificatyon based on ordinary regularity is the special case of d=1).
Another important class of graph algorithms are those based on matrix/spectral approaches. It has traditionally been much more difficult to find counter-examples to them. However this is not because spectral algortihms are so good, it is merely because human intuition works well with visually appealing notions of various "regularity" in terms of graphs, but rather fails when working in matrix representation. I do personally know people who have (or had) the intuitive insight into matrices, but this is a rather uncommon trait ( it may be related to the way how human brain works; it reminds me of the film about an autistic kid who could crack ciphered texts by merely looking at them on the computer monitor. I forgot the movie title. Can someone remind me please?)
I hope my explanations somewhat clarify the issue of which graphs are difficult and for which algorithms. Twri (talk) 17:36, 24 November 2008 (UTC)
  • "some graphs with more than 500 vertices are difficult for graph isomorphism" -- molecular graph with 500 vertices looks like too big for usual chemical tasks. Many matrix/spectral and other approaches are sencetive for vertex degree. "regular mesh graphs are not regular graphs" -- why? may be regular mesh graphs are not graphs?  ;-) "and plays no further role and being quite fast gives no serious deterioration of computational complexity", but well-known Nauty has problems for regular graphs, also "computational complexity" is theoretical estimation for the algorithm, but we talk about applications and performance here!--Tim32 (talk) 14:09, 25 November 2008 (UTC)
  • PS. Herndon, Nechepurenko, Popkov, Zemlyachenko, Korneenko, Tyshkevich, Foggia, Sansone, Vento, Trofimov, Smolenskii wrote that some types of regular graphs are difficult for number of practical GI applications, but User:Twri wrote here "regular graphs are not difficult"! -- WP:NOR!!!--Tim32 (talk) 14:43, 25 November 2008 (UTC)

Paragraph about chem app

Okay, here's my shot at a para based on the above info, beginning with the existing text.

In cheminformatics and in mathematical chemistry, graph isomorphism testing is used to identify a chemical compound within a chemical database. [1] Also, in organic mathematical chemistry graph isomorphism testing is useful for generation of molecular graphs and for computer synthesis. A variety of domain-specific heuristic graph isomorphism algorithms have been developed for chemistry applications that have been empirically determined to perform well on average in this context.

What do you think? Dcoetzee 21:23, 24 November 2008 (UTC)

Sounds good, although I think that in practice molecules are searched and identified using simple string comparison (once a canonical string such as an InChI or canonical SMILES has been generated for all the compounds in the database and for the query). Perhaps the movie you are thinking about is Mercury Rising? --Itub (talk) 21:51, 24 November 2008 (UTC)
  • Well, I didn't write the first two sentences - that's existing text from the article. But I'm glad you like it so far. :-) I still need references for the new sentence. Dcoetzee 21:56, 24 November 2008 (UTC)
  • Mercury Rizing" - yes it is the one. About SMILES: for small molecules it is certainly so, but for larger ones the computation of SMILES (or other string form), i.e., graph canonization may take longer time than the direct graph matching. Not to say that SMILES stuff is for human readability. I am pretty sure, commercial chemical databases use something "human unreadable", for efficiency, both in runtime and memory. Second, I find it strange that the article chemical database does not mention graph isomorphism, but mentions subgraph isomorphism. Also, the sentence about generation and synthesis requires (1) explanation how they are used, (2) references, and (3) the corresponding text in the corresponding chemical articles. (...and a nitpicking 4): "[[Combinatorial chemistry|computer synthesis]]" is a bad example of link piping in this sentence. Third, about the "domain-specific": the words "on average" must be deleted. In mathematical sense it requires proofs (which are scarce), and in "intuitive" sense a better choice IMO is "almost always". The situation is kind of similar to simplex method: it has been working well in practice, but nobody knows why. In any case, you are right: this kind of a generalized statement much come only from a recognized expert in the domain, i.e., citation is required. And when you find a good citation, then you most probably will find a better way to say what you said. Twri (talk) 22:57, 24 November 2008 (UTC)
You only need to canonize the molecules on the database once, so in practice you only need to do one canonization per query, regardless of the number of molecules in the database. For large enough databases canonization is generally more efficient. --Itub (talk) 07:15, 25 November 2008 (UTC)
Yes, you are right, "one canonization per query", just the same as "one graph isomorphism per query". And I don't see on what grounds you argue that "canonization is generally more efficient". `'Míkka>t 15:52, 25 November 2008 (UTC)
Again SMILES does not work correctly for cuneane! Again, we found that there are not official experts in Wiki to solve "is it true?" problems, so we should not try to solve "is it true?" for methodology of GI applications, but you suggested your original methodology here: "You only need to canonize the molecules on the database once". Again, see the article by Trofimov and Smolenskii about chem. database etc. "The situation is kind of similar to simplex method: it has been working well in practice, but nobody knows why." -- it is false - there is another situation in chemistry: The fact is that not only canonization approach and heuristic algorithms are used for chemical GI applications, but also strong proved approach by Trofimov and Smolenskii.--Tim32 (talk) 14:34, 25 November 2008 (UTC)
I may start thinking of it as "used, strong and proved" when I see it cited by other people. I didn't know that this trivial use of caching was an original invention of mine. Maybe I should patent it and get rich! As for cueneane, this may have been a problem of the original canonical SMILES paper, but the SMILES notation can be used independently of the canonicalization algorithm that is chosen, and it is possible to use an algorithm that doesn't have a problem with cuneane. It would be interesting to test all the free and commercial implementations and see how they do with cuneane (that would be original research, of course, but maybe you could even publish it in a journal!). It is possible that some of them won't care about getting cuneane wrong, since most of their customers only care about useful molecules. ;-) --Itub (talk) 15:10, 25 November 2008 (UTC)
Hardly you get rich: you still need a heavy canonization step for query molecules regardless how well you cached and indexed the database: this is major difference from, say, search people by social security number or restaurants by location. `'Míkka>t 15:52, 25 November 2008 (UTC)
Please let me point out an often overlooked aspect of comparing commercial implementaitons: unlike published algorthms "cast in paper", implementations are live things: once you run a comparison and find, say, contner-examples, then if a commercial product wants to survive, this finding will be filed as a bug to be fixed.Twri (talk) 15:59, 25 November 2008 (UTC)

Once again, I surrest to stop this demonstration of personal smarts in the polemic with the non-stop glorification of "Trofimow and Smolenskii" and focus on the improvement of the article by expanding it using publications of recognized experts in the domain, as wikipedia scriptures teach us. `'Míkka>t 15:52, 25 November 2008 (UTC)

Once again, Herndon, Nechepurenko, Popkov, Zemlyachenko, Korneenko, Tyshkevich, Foggia, Sansone, Vento are not recognized experts for you also!--Tim32 (talk) 13:31, 26 November 2008 (UTC)
"I may start thinking of it as "used, strong and proved" when I see it cited by other people" -- again, it cited by other people: arXiv:0711.2010v4.--Tim32 (talk) 13:39, 26 November 2008 (UTC)
A long time period nobody here could find any better algorithm for practical usage in organic chemistry. But everybody wants to delete only one existed! Very "productive" work as well as absurd work!--Tim32 (talk) 20:38, 3 March 2009 (UTC)
  1. ^ Christophe-André Mario Irniger (2005) "Graph Matching: Filtering Databases of Graphs Using Machine Learning", ISBN 1586035576
Retrieved from "https://wiki.riteme.site/w/index.php?title=Talk:Graph_isomorphism/Archive_1&oldid=1136774714"