Are there any REAL applications of Graph Isomorphism?
Computational Complexity 2024-02-11
Lance's post on Babai's result on Graph Isomorphism (henceforth GI) inspired some random thoughts on GI. (Lance's post is here.)
1) Here is a conversation with someone who I will call DAVE. This conversation took place in the late 1980's.
BILL: You got your ugrad degree in engineering and then went to CS grad school. You are a pragmatic guy. So why did you work on graph isomorphism?
DAVE: My advisor was working on it. The 1980's was a good time for GI: the problems restricted to bounded genus, bounded degree, and bounded eigenvalue multiplicity were proven to be in P. Tools from Linear Algebra and Group Theory were being used. People thought that GI might be shown to be in P within the next five year. Then it all stopped for quite some time.
But back to your question about GI being practical, I asked my advisor for real applications of GI. He said:
Organic Chemists use graph isomorphism to match chemical structures.
By the time I found out this wasn't true, I already had my PhD. I quickly switched to Computational Geometry which really does have applications. Maybe.
2) So why was graph isomorphism studied? Much to my surprise, a survey by Grohe and Schweitzer (see here) says that
Graph isomorphism as a computational problem first appeared in the chemical documentation literature of he 1950's (for example Ray and Kirsh) as the problem of matching a molecular graph against a database of such graphs.
(The article by Ray and Kirsh is here.)
So at one time it was thought that GI would apply to Chemistry. Did it? I suspect some simple algorithms and heuristics did, but (1) chemicals are more complicated than graphs, and (2) by the time we are talking about graph isomorphism of bounded eigenvalue multiplicity, the algorithms got to complicated to really use. BUT these are just my suspicions (what is the difference between a suspicion and a guess?) so I welcome comments or corrections.
2) The same article also says:
Applications [of GI] spans a broad field of areas ranging from Chemistry to computer vision. Closely related is the problem of detecting symmetries of graphs and of general combinatorial structures. Again this has many application domains, for example, combinatorial optimization, the generation of combinatorial structures, and the computation of normal forms.
That sounds impressive, but I would like to know if the applications are to the real world, or are they do other theory things.
3) The prominence of GI in the CS theory literature is because its one of the few natural problems that is in NP, not in P, but not known to be (and unlikely to be) NP-complete.
4) Graph Isomorphism IS a natural problem. What is an unnatural problem?
BILL: Do you find the following interesting: There is an r.e. set that is not decidable and not Turing-equivalent to HALT.
DARLING: Yes. Unless it was some dumb-ass set that people like you constructed for the whole point of being r.e., not decidable, and not Turing-equivalent to HALT.
BILL: You nailed it!
5) So, is GI in P? This is truly open question in that it really could go either direction. There is no real consensus.
6) I have heard that Babai's result is as far as current techniques can take us. So we await a new idea.