With the Foundations of Software Technology and Theoretical Computer Science Conference 2011 just four days away and the prospect of getting a glimpse of the likes of Umesh Vazirani, Moshe Vardi and Madhu Sudhan exchanging ideas and insights right in our campus delightfully imminent, I, Karthik and Surya are quite excited about the whole affair. Not to mention that this is going to be the first major conference we’ll be attending. So, we three have been warming up for whirlwind of a week that it’s going to be with all the talks and workshops by thinking about one of the most beautifully cruel problems of the trade, one that all the three have common ground in. Namely, the Graph Isomorphism problem, henceforth referred to as simply GI.
The statement of GI is pretty straightforward – given two finite graphs and , determine whether there exists a bijection from the set of vertices of to that of so that given two vertices and in , and are adjacent in if and only if and are adjacent in . In other words, determine whether the graph may be turned into the graph by a mere relabeling of vertices.
In a sense, graph isomorphism is to graph theory what coordinate transformations are to physics – mathematically relevant and meaningful results ought to be independent of how the vertices are labeled just as physically meaningful statements about natural phenomena ought to be independent of how our coordinate grid is laid out, somewhat in the spirit of that celebrated quip attributed to Fritz Zwicky.
GI, as a problem, is hence one of great interest, and this is all the more accentuated by the fact that we don’t know where it fits in the grand landscape of algorithmic complexity. Is it solvable in polynomial time? Is it NP-complete? As of now, these questions still remain unanswered.
So, this is the problem that we (as in, we the Triumvirate) have taken upon. Of course, everyone would like to see label-independent descriptions of graphs à la manifestly covariant formulations of dynamical laws in physics, but it’s hard to do that in an unambiguous and general way. For instance, a graph with ‘six vertices, all of degree two’ describes a hexagon as well as a Star of David, which are clearly non-isomorphic. Of course, we could impose further conditions of connectedness et cetera but that doesn’t adhere to the ideal of generality. With the above in mind, the Triumvirate has decided to begin by developing alternative ways of looking at graphs which hopefully shall shed some light on this matter, if we are lucky enough. And this is what we came up with.
Consider an object which I shall call grof (no, nothing to do with the psychiatrist) that consists of finitely many things called groficles. I’m deliberately choosing highly nonstandard, not to mention, funky, terminology to obscure how things tie up to the usual notion of graphs. Maybe I’m being too hard-nosed as a mathematician but then the prospect of preexisting notions getting in the way is too habitual a risk when we’re trying to look at things in new ways. Now, back to grofs. So, a grof consist of elements called groficles that satisfy the following axioms.
- For every groficle , there is a partition of into three equivalence classes, of which one is singled out as the zero class .
- Given two distinct groficles and in , if , then .
- Given three pairwise distinct groficles , and in , if and , then , where is the equivalence relation induced by the partition (in other words, amounts to saying that and belong to the same equivalence class in the partition ).
And now for the recipe for turning the confunding mess above into something more palatable. Let’s start by picking up an arbitrary groficle in . Now, it is quite possible that one or more of the equivalence classes in are empty, but that really isn’t much of a bother as all the assertions that are to follow hold for empty sets trivially. So, without loss of generality we treat all our equivalence classes as nonempty. Also, we’ll let, as the standard convention goes, denote the equivalence class in that contains . And now, we make the assertion:
If , then .
Proof: The antecedent in the above conditional, , is just another way of saying that . The groficles and belong to both and , so, we consider a groficle which is different from both and . Since is different from , it must belong to , which means . Now, if , then, by virtue of Axiom 3, we would have which is a contradiction. Hence, we conclude, , or in other words, , which further implies, . Thus, . Now, by Axiom 2, we know implies , which means we can interchange and in the above argument to obtain . Putting the two together, we end up with . Q. E. D.
What we have essentially shown here is that we can take one of the two nonzero equivalence classes of any groficle, add the groficle in question to it to obtain a set which we’ll call for now, remove another groficle from it and get one of the nonzero equivalence classes of the second groficle in question. The set represents a rather nice democratic situation, which calls for some more funky terminology – all the groficles with are elements of are said to canoodle with one another at the canoodlarium . (It is common knowledge among differential geometers that the life of the author may be foliated by a stack of Forever Alone memes. *whimper*)
A few quick observations: since for any given groficle , there are exactly two disjoint nonzero equivalence classes in the partition , there are exactly two distinct cannodlaria associated with it. The two canoodlaria are necessarily nonempty – they both contain at least the groficle . Given two arbitrary canoodlaria and , they may either be disjoint or contain exactly one groficle in common. What if two distinct canoodlaria had at least two distinct groficles, say and , in common? Then the two nonzero equivalence classes in would be and . But then, . The two equivalence classes in the partition are thus not disjoint, which is a contradiction.
So this is how this whole grof business we’ve been at ties up with the familiar notion of graphs. The canoodlaria become the vertices, with disjoint canoodlaria corresponding to non-adjacent vertices, and the groficles in the intersection of the two canoodlaria corresponding to the edges. Axiom 1 says that an edge may or may not be linked with another edge, and if linked, it can do so in two ways (i.e. through its two vertices). Axiom 2 says that the relation of being linked is a symmetric one. Axiom 3 says (in a very disguised fashion) that if the edges in question link through the same vertex, then the relation of being linked is also a transitive one. However, there are a few important differences that have to be kept in mind as well. Firstly, our construction doesn’t allow for the possibility of loops (since there have to be exactly two canoodlaria associated with each groficle) or multiple edges (since there can be at most one groficle for every pair of canoodlaria). And secondly, isolated vertices are meaningless as they correspond to empty canoodlaria and all empty canoodlaria are set theoretically the same. This isn’t undesirable at all, for as far as GI is concerned, loops, multiple edges and isolated vertices only lead to increased paperwork and are as useful as complimenting a girl you’ve just chatted up over a drink about how she is topologically equivalent to a five-holed blob.
In fact, I think I’ll go the whole hog and tout our grof formalism as being better adapted for the analysis of GI than the plain old ‘vertex-ey’ way of doing things. This, by itself, is of course a rather dangerous statement to make for multiple reasons, a heightened probability of a nuclear holocaust not being one of them. The notion of functions on grofs, where edges aka groficles are mapped to edges aka groficles, is markedly different from the notion of functions on graphs, where vertices are mapped to vertices, and it makes no sense to directly compare them. What is legitimate is that we first define what a grof-isomorphism is in parallel with a graph-isomorphism.
Given two (finite) graphs and , a graph-isomorphism is a bijection from the set of vertices of to that of such that given two vertices and in , and are adjacent in if and only if and are adjacent in .
Given two (finite) grofs and , a grof-isomorphism is a bijection from the set of groficles of to that of such that given some groficles (where belongs to a finite indexing set) in , canoodle with one another in if and only if canoodle with one another in .
And then we can ask, given two graphs and which may be recast as the grofs and respectively, whether the existence of a graph-isomorphism between and implies the existence of a grof-isomorphism between and , and vice versa. The answer to that is of course affirmative and the argument is pretty straightforward and constructive. Because, between two adjacent vertices (aka non-disjoint canoodlaria) and , there is exactly one edge (aka the lone groficle in ), given a graph-isomorphism , we may define a corresponding grof-isomorphism by its action . This is well-defined as graph-isomorphisms take adjacent vertices to adjacent vertices. Conversely, given a grof-isomorphism , we may define a corresponding graph-isomorphism by the action . This is well-defined as grof-isomorphisms take canoodling groficles to canoodling groficles.
And finally it’s time to ask the hard questions. What is the point of the above? Why do I think an ‘edgier’ approach has an edge over the usual vertex-based ones? To be honest, the most convincing answer that I’ve been able to come up with is that this is quite, what is it that the hipsters say… ah! ‘Underground’! And the second most convincing answer (trivially so; I don’t find it very convincing) is that since grof-isomorphisms are far more stringent than any self-respecting graph-isomorphism could ever hope to be, there are far more ways in which the former may fail to exist. Computationally, this means things are easier to weed out – indeed, most non-isomorphic graph-pairs don’t even have the same number of edges to begin with! But whether this translates to some nice and hopefully earth-shattering insights into richness of mathematical structure that graph theory has to offer, we still have to see.