Talk:Graph isomorphism

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated Start-class, Mid-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
Mid Priority
 Field: Discrete mathematics
WikiProject Computer science (Rated Mid-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
 ???  This article has not yet received a rating on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.
 

Software review[edit]

There seems to be a need to start this discussion. The article badly needs a more or less comprehensive review of available software for testing graph isomorphism. Here is just a couple of reasons for that:

  1. Testing graph isomorphism is of great practical importance; despite the uncertainty about its theoretical complexity, people still want to solve this problem in practice.
  2. Even if the worst case is hard to solve, many problem instances are easy and can be resolved by simple heuristics (e.g., the most trivial perhaps is comparison of the number of vertices of two graphs).

I started the section Software today but to my surprise some trolls immediate came into play and started deleting my additions without any explanation. Well, one of my items was indeed not that suitable for Wikipedia (thanks to Twri for pointing that out) but the others perfectly make sense. David Eppstein deleted my recent addition of a link to Combinatorica package for Mathematica CAS, motivating that it is "not primarily about isomorphism and would be several positions down on a list of notable isomorphism implementations". I believe that is not a legitimate reason for deletion since:

  1. This is a reputable package for widely used Mathematica CAS.
  2. This packages contains functions for testing/finding graph isomorphism and that makes it very relevant to including into Software section of Graph isomorphism article. It may be not "not primarily about isomorphism" as it contains a bunch of other discrete mathematics related functions, but that does not neglect its abilities of solving graph isomorphism problems.
  3. The statement about benchmarking is also an irrelevant argument: first, it is subjective without an appropriate citation; second, even if this package is not a state-of-art tool for graph isomorphism problems, it is still useful for many problems of this kind (and many users of Mathematica).

Based on the above explanation, the link to Combinatorica package should be restored in Software section. Maxal (talk) 00:18, 3 March 2009 (UTC)

The primary objection is adding external links without addition of encyclopedic content, especially about software and packages. Wikipedia is a repository of encyclopedic information about notable things described in reliable sources. A mere link to any software package is useless from these points of view and often look dubious: after all, people can use google themselves to find out what else in on web. I agree that a section about implementations is badly missing. And a proper solution would be to add it, to describe implementations other people (besides authors, friends and family members) think notable and state so in published materials. In particular, in the case at hand, if it is known which algorithm is implemented in Mathematica, then it may be briefly mentioned here. Otherwise a ref to Mathematica is of low relevance: it has thousands of functions, but we are not going to include external links to Mathematica into thousands of wikipedia articles. - 7-bubёn >t 00:35, 3 March 2009 (UTC)
The authors of Combinatorica are respected scientists, there is a book published about solving problems with the Combinatorica package - isn't that all make this packages "notable"? Maxal (talk) 00:42, 3 March 2009 (UTC)
It may be notable as a software package in general and yet not sufficiently notable in the much more specific context of implementations of graph isomorphism algorithms. —David Eppstein (talk) 00:55, 3 March 2009 (UTC)
But it is notable enough for Mathematica users etc. Anyway, these all are still just subjective opinions. The facts are: it is a notable package, it is able to solve (some) graph isomorphism problems; and that makes it relevant for mentioning it in the current Wikipedia article. Maxal (talk) 01:07, 3 March 2009 (UTC)
(Edit conflict) See our guidelines on external links, regarding what sorts of links include: “A well-chosen link to a directory of websites”. We already include such a well-chosen link, to Skiena's SUNYSB listing of graph isomorphism implementations. Therefore, we don't need to duplicate the contents of that link ourselves: Wikipedia is not a web directory. Additionally, it seems against our policies on maintaining a neutral encyclopedia to push for the inclusion of this link, for a package of routines for a specialized commercial piece of software (Mathematica) that only includes isomorphism as one among a large number of other routines, and not to push for links to highly-regarded packages that are specific to graph isomorphism such as Nauty. (For more on the relative significance of these different implementations, the ratings on the SUNYSB site might be relevant.) I continue to feel that the link to Combinatorica should not be included: there are five more-deserving links included on the SUNYSB list, and including all of them would head more towards being an indiscriminate web directory than being an encyclopedia. —David Eppstein (talk) 00:36, 3 March 2009 (UTC)
I don't see why a link to Skiena's should prevent from mentioning various "notable" software implementations in Wikipedia article. Also notice that the package Combinatorica is not commercial itself (it is run under commercial Mathematica software but that does not make it commercial; and Mathematica is already described in Wikipedia). Links to other reputable software implementations are welcome as well. And there are not so many of them, so the article won't be "directory of websites" even if we include them all. Maxal (talk) 00:53, 3 March 2009 (UTC)
  • Actually, Combinatorica is commercial, and not particularly a particularly good implementation of a graph isomorphism algorithm. (I'm a Mathematica user, and I cannot use Combinatorica without purchase.) — Arthur Rubin (talk) 01:31, 3 March 2009 (UTC)
That's a non-sense. The package is freely available for download from the official website and distributed in the form of plain text Mathematica source code. Moreover, its header mentions the following licence:
This package may be copied in its entirety for nonprofit purposes only.
Sale, other than for the direct cost of the media, is prohibited.  This
copyright notice must accompany all copies.

Maxal (talk) 02:00, 3 March 2009 (UTC)

  • The link to Skiena's explains that Mathematica uses Combinatorica package for GI, hence a separate link to Mathematica is redundant and constitutes an inexact credit. - 7-bubёn >t 01:31, 3 March 2009 (UTC)
The purpose of mentioning Mathematica is to indicate that the package won't run without it (i.e., this package is not a standalone application). Maxal (talk) 02:04, 3 March 2009 (UTC)
Software I develop will not run without Microsoft Foundation Classes, yet my company does not put Microsoft in the first lines of its ad brochures. Hey, even with Microsoft it will not run without Intel chips. There is a healthy intellectual property threshold, and I don't believe it is inside Mathematica, rather than outside it, unless you present a solid proof otherwise. - 7-bubёn >t 02:16, 3 March 2009 (UTC)
I explained why I gave a link to Mathematica - but I would not care if it is not mentioned at all. It is more important that Combinatorica package (and similar software) should be listed in the article. Maxal (talk) 02:21, 3 March 2009 (UTC)
<sigh>. Let me reiterate: you may list anything you want sufficiently relevant, provided the you supply your additions with references to independent reliable sources which speak for notability and relevance of the software in question. These are among the most fundamental rules governing the content of wikipedia. A simple addition of external links to software packages does not conform these rules. - 7-bubёn >t 02:30, 3 March 2009 (UTC)
Oh, I see now what you meant under "link to Mathematica". A brief search discovered, in particular, a book about teaching discrete math in high school; and a book about randomness in physics that both explicitly mention Combinatorica's graph isomorphism testing function IsomorphicQ. I bet there other similar references exist. Maxal (talk) 02:58, 3 March 2009 (UTC)

Tim32 behavior[edit]

I suggest to file a formal complaint against Tim32, since it appears that he persistently refuses to accept the local consensus. Despite all arguments seen above, there is no evidence of the possibility of peaceful resolution. I cannot do it myself, since I am not well versed in wikilawyerese, but I will second the motion. - 7-bubёn >t 20:21, 3 March 2009 (UTC)

If the problems with Tim32 continue, I recommend consulting Wikipedia:Mediation Cabal, where some informal dispute resolution could occur. Dcoetzee 19:34, 10 March 2009 (UTC)
The edits of User:Tim32 on this page look like self-promotion to me. That falls under the 'promotional editing' clause of our Conflict of Interest guideline, which is explained under WP:COI#Blocks. I think that we are getting close to the point where Tim32 should be given a final warning against inserting reference to his own work into Wikipedia articles. EdJohnston (talk) 20:28, 10 March 2009 (UTC)

Now he's trying it at Graph isomorphism problem: [1]. — Emil J. 12:28, 24 June 2009 (UTC)

GI in chemistry[edit]

The article about GI applications in chemistry by Trofimov and Smolenskii cited in Arjeh M. Cohen , Jan Willem Knopper and Scott H. Murray, Automatic Proof of Graph Nonisomorphism, Mathematics in Computer Science, 2008, doi 10.1007/s11786-008-0052-8 --Tim32 (talk) 08:31, 10 March 2009 (UTC)

It is mentioned in passing; even the second author's name is screwed up, which speaks of notability :-) No minimal discussion of the essence. - 7-bubёn >t 18:59, 10 March 2009 (UTC)
See, Google scholar--Tim32 (talk) 22:54, 11 March 2009 (UTC)
Yes, Google scholar does not find any citation to the paper you are pushing, we already know that. What was your point then? — Emil J. 10:50, 12 March 2009 (UTC)
No, Google scholar found: Arjeh M. Cohen , Jan Willem Knopper and Scott H. Murray, Automatic Proof of Graph Nonisomorphism, Mathematics in Computer Science, 2008, doi 10.1007/s11786-008-0052-8--Tim32 (talk) 11:42, 12 March 2009 (UTC)
No it did not. This is not the first time this user supplies us with info which he did not bother to verify himself. - 7-bubёn >t 17:19, 12 March 2009 (UTC)
You did not find "doi 10.1007/s11786-008-0052-8" ? You did not find Automatic Proof of Graph Nonisomorphism paper  ? You did not find "Trofimov" in this paper? (See, ref [23] on page 19)--Tim32 (talk) 22:15, 12 March 2009 (UTC)
I did not find it in Google scholar you provided. I have already described my findings. - 7-bubёn >t 23:14, 12 March 2009 (UTC)
Click the link Google scholar, click link "Cited by 1" under the reference to the paper, Direct link Ok? --Tim32 (talk) 09:31, 13 March 2009 (UTC)
You should have started from "direct link" in the first place. We are not to solve internet maze puzzles here. - 7-bubёn >t 16:12, 13 March 2009 (UTC)
You should have started from google help! If your skills in Computer Sci. area are so low, then let you stop to write to this page as well as to other computer sci. pages, before you will improve your skills to search in google.--Tim32 (talk) 16:31, 13 March 2009 (UTC)
PS. BTW, special Russian joke: кто играет 7 бубен - тот бывает зае... :)
Yep, I play preferans and that's what happened to me in wikipedia, hence the name. - 7-bubёn >t 20:12, 13 March 2009 (UTC)
OK, so it appears it was referenced. Once. That doesn't make it notable. — Arthur Rubin (talk) 19:34, 13 March 2009 (UTC)
Where had been written the rule: if Once, then That doesn't make it notable? How much you need? :))) Is it seriously?! :) --Tim32 (talk) 22:02, 13 March 2009 (UTC)
7-bubёn! Sorry for your nic-name, but it seems you had selected this one especially for similar jokes ;)--Tim32 (talk) 22:02, 13 March 2009 (UTC)
BTW, Ребята, раз вы все так хорошо понимаете по-русски, может, мы наши проблемы выясним на этом языке :)--Tim32 (talk) 22:02, 13 March 2009 (UTC)
Translation: "Guys, once you understand so well in Russian, can we find out our problems in this language" Do not post in foreign languages on the Engish wikipedia please unless you provide a translation or strong justification, it is against policy and rude. Verbal chat 13:47, 24 June 2009 (UTC)
I guess it was a joke no one bothered to comment. Please cite the policy you refer to. From my side, WP:AGF: if you cannot understand it, ignore it, unless it has implications on article content. After all, some write in English no one can understand :-) - Altenmann >t 15:29, 24 June 2009 (UTC)
Was that a Google translation? AFAICS, it reads "Guys, since (or once?) you all understand Russian so well, maybe we will settle our problems using this language", not "find out". Anyway, as Altenmann said, it is a harmless joke. Gosh, it even sports a smiley. — Emil J. 16:04, 24 June 2009 (UTC)

Complexity[edit]

The article says,

it is one of a very small number of problems belonging to NP neither known to be solvable in polynomial time nor NP-complete.

This seems doubtful to me since problems in NP are assumed to *not* be NP-Complete until proven otherwise. The next statement also seems dubious:

one of only two of that list whose complexity remains unresolved.

I don't know the upper bound for the time complexity of determining whether two graphs are isomorphic, but I'm quite sure a bound is known. Jwesley78 22:56, 31 March 2010 (UTC)

Your "this seems doubtful to me" statement makes no sense to me. It is true that:
  • At the time Garey and Johnson wrote their book, most "natural" problems in NP (natural in an intuitive sense meaning that researchers had looked at them as important problems to solve in some application area) were either known to be polynomial time or known to be NP-complete. Garey and Johnson listed a small number of exceptions as "open problems", of which Graph Isomorphism was one.
  • The complexity of all but two of their open problems has been resolved, in the sense that a polynomial time algorithm or an NP-completeness proof has been found. Graph isomorphism is still unresolved in this sense.
  • There are now a few other natural problems that are similarly known to be in NP, not known to have a polynomial time algorithm, and not known to be NP-complete. But just as it was true when Garey and Johnson wrote it, this set of problems is still small in comparison with the set of problems for which polynomial time algorithms or NP-completeness has been proved.
As for "a time bound is known", that is very different from determining whether it belongs to P or whether it is NP-complete, both of which are binary and mutually exclusive possibilities. Of course it might be possible to prove that (with the assumption that P≠NP) GI is neither in P nor NP-complete; that would also be a major result and is also still unknown. —David Eppstein (talk) 23:41, 31 March 2010 (UTC)
OK, I need a little more clarification:
  1. I've run across many problems which are in NP , but are not known to be NP-complete or solvable in polynomial time. Perhaps, these would not be considered "natural problems"? I mentioned integer factorization, and discrete logarithm in my first comment, but also several graph recognition problems, e.g., unit distance.
  2. I'm showing my ignorance of complexity theory. Since it is known to be in NP, what is meant by "complexity remains unresolved"? I understand what you are saying, but saying it this way seems unclear to me. 01:10, 1 April 2010 (UTC)
Thanks, Jwesley78 00:44, 1 April 2010 (UTC)
Saying that its complexity "remains unresolved" seems to assume that the problem is actually NP-complete or in P, but we're just not sure which one yet. It could very well be in neither. Integer factorization, for example, seems unlikely to be NP-complete, and equally unlikely to be in P (at least we all hope so!). Jwesley78 01:45, 1 April 2010 (UTC)
Factorization is the other one on Garey and Johnson's list (or actually I think it was primality testing, which is now resolved, but close enough). Yes, there are other unresolved questions, but not large numbers of them in comparison to the large number of polynomial algorithms and the large number of NP-complete problems now known. As for "remains unresolved", a proof that (assuming P≠NP) the problem is neither in P nor NP-complete would also be a resolution. —David Eppstein (talk) 01:50, 1 April 2010 (UTC)
I found an article from 2007 called "A Polynomial Time Algorithm for Graph Isomorphism". Here is the link http://arxiv.org/abs/0711.2010 I guess it means graph isomorphism doesn't belong to NP. (Jurica Tot (talk) 13:15, 11 April 2010 (UTC))
Now I found yet another link to polynomial time algorithm for graph isomorphism also on the first page of google search for graph isomorphism algorithm. Here it is http://www.dharwadker.org/tevet/isomorphism/ They weren't there few weeks ago when I created my own polynomial algorithm. It's my bad luck. Jurica Tot (talk) 13:33, 11 April 2010 (UTC)
Those papers are not peer reviewed and may well be wrong. In particular, for the arxiv one, arxiv's standards are to allow papers to be published even if the moderators think they're incorrect as long as they're on-topic. The Czerwinski arxiv one you point to is far from the only one to claim to prove the problem polynomial; it spends a lot of time and effort proving the obvious facts that for instances that are isomorphic it will say they are but it doesn't seem to have any attempt at a proof that non-isomorphic instances will be correctly distinguished from each other. —David Eppstein (talk) 16:40, 11 April 2010 (UTC)
@Jurica Tot. Re: "I guess it means graph isomorphism doesn't belong to NP". The problem is in NP b/c a solution (or "certificate"), which in this case would be a bijective mapping of vertices in one graph to vertices in the other, can be verified in polynomial time; P is a subclass of NP. The assumption is that, if P != NP, that P is disjoint from NP-complete. Justin W Smith talk/stalk 17:34, 11 April 2010 (UTC)

Good, reliable source[edit]

There is a good paper from 1977 summing up approaches to graph isomorphism until then, search for "The Graph Isomorphism Disease" from Ronald C. Read and Derek G. Corneil. — Preceding unsigned comment added by 134.93.143.232 (talk) 11:29, 11 October 2013 (UTC)

It is about Graph isomorphism problem; listed there, too - Altenmann >t 08:32, 8 January 2014 (UTC)

Laymans definition[edit]

I took the liberty of adding a laymen's definition near the top of the article for the less mathematically inclined to form a concept of the subject. As a programmer, it took me a few minutes of rereading the opening section to decipher what a graph isomorphism is - I am sure my definition can be reworded to be more precise but still maintaining readability for non mathematicians that have an interest in this Wikipedia article (we do exist). I realise the 'simple english' Wikipedia site exists but surely there can be a middle ground Norlesh (talk) 11:49, 7 January 2014 (UTC)

I'm afraid I don't understand that definition, so I can't suggest a rewording which makes sense and is much less complicated than the formal definition. However, as a mathematician, I couldn't report on what makes a definition understandable to the layman. Perhaps:
Two graphs are isomorphic if they have the same number of vertices and there are numberings of the graphs so vertex pairs with the same numbers are connected in one graph if they are connected in the other.
(Emphasis added to note where the mapping between the graphs corresponds.) — Arthur Rubin (talk) 17:14, 7 January 2014 (UTC)
I agree that this is an improvement over Norlesh's attempt at a definition, which could easily be misread to imply (incorrectly) that all 3-regular graphs on the same numbers of vertices are isomorphic. —David Eppstein (talk) 19:21, 7 January 2014 (UTC)
He-he, this is the trouble with "layman's" definitions: you have to try really hard to make it readable and reasonably correct and unambiguous . The second version is not (quiz: find 7 reasons why :-). Now, again, does a layman know what is graph? May be he thinks it is a chart? To avoid the latter problem I'd suggest to put the informal definition into section "example" and rename it 'Informal definition'. Now we still need a 'GI for Dummies' ... - Altenmann >t 08:49, 8 January 2014 (UTC)
Something like this: "A graph labeling is an assignment of a unique label to every vertex of a graph. Two graphs are said to be isomorphic if they have the same number of vertices and there are labelings of the two graphs such that two labels are connected by an edge in one graph if and only if they are connected by an edge in the other." - Altenmann >t 09:15, 8 January 2014 (UTC)
(quiz: find 3 problems with this definition :-) - Altenmann >t 09:17, 8 January 2014 (UTC)