Group-theoretic techniques

Group theory crops us simply everywhere in theory of computing -- a seminar on ``Group-theoretic techniques in computer science'' would run on into weeks. All we could hope for was a good sample. We got a wonderful one.

Arvind showed us how group theory was used effectively to solve what looks like a purely graph-theoretic problem. The problem is to decide if two given graphs, of bounded degree (in fact most of the exposition was for graphs with max degree 3), are isomorphic. Without the degree restriction, graph isomorphism is the celebrated and well-studied ``intermediate'' problem -- unlikely to be NP-complete, not known to be in P, but no known lower bounds better than NLOG. For bounded degree graphs, there is however a polynomial time algorithm.

The intuition behind how this algorithm works on trivalent graphs is roughly as follows: Consider the graph $G$ which is disjoint union of $G_1$ and $G_2$, and look at its automorphism group $A$ (elements are vertex relabellings which preserve adjacency; the group operation is composition of labellings). If the graphs are isomorphic, then $A$, and hence any generator set for $A$, has elements which map a vertex of $G_1$ to a vertex of $G_2$. The converse is also true. So it suffices to compute a generator set for $A$. But this may not be an easy task. How can one nonetheless use this idea?

Let $e_i$ be an edge of $G_i$, $i=1,2$. Subdivide both $e_1$ and $e_2$ and connect the division points $u_1,u_2$ by new edge $e$; this gives another trivalent graph $H_e$. Now $G_1$ and $G_2$ are isomorphic iff for some such $e$, there is some element of Aut($H_e$) that flips the endpoints of $e$.

We are back to computing the generator set of the automorphism group of a graph. But the graph is trivalent, and hence the automorphism subgroups stabilising individual edges ($A_0$ below) are 2-groups. Furthermore, and this is crucial, the graph has a special edge $e$, a bridge between two parts, and this provides the key to an incremental construction as follows: For graphs $X_r$ of increasing ``radius'' centred around the edge $e$ (strictly speaking, $X_r$ consists of all length $\le r$ paths containing $e$), figure out the ways in which these vertices/edges can be relabelled preserving adjacency. (For distance 0, only two labellings are possible: identity, and the map that flips $u_1$ and $u_2$.) From each such set of permissible relabellings, now figure out permissible relabellings for adjacent edges/vertices.

Group theoretically, construct generator sets for the automorphism groups $A_r$ of $X_r$. Each $A_{r+1}$ restricted to $X_r$ is in $A_r$, and the natural homomorphism from $A_{r+1}$ to $A_r$ has as kernel those relabellings that pointwise fix $X_r$. Given a generator set for $A_r$, we can first figure out this kernel, and then use it to find a generator set for $A_{r+1}$. Eventually we construct $A_n$, which has the information we need.

The incremental construction requires polynomial time (poly in $n$) algorithms for the following group-theoretic questions: given a group (which is a subgroup of $S_n$) presented by a generator set, (1) find the group size. (2) test for membership in the group. (3) given poly time membership testing for a ``large'' subgroup, find a generator set for the subgroup. In describing the algorithms, we were led through a nice exposure of solvability, orbits, stabiliser subgroups, blocks and primitivity, blocks and subgroups, block systems, Jerrum's filter, Schreir's generator, and more. One had to remind oneself periodically that this delving deep into the fascinating world of groups was being done at that point just to address graph isomorphism! The original paper describing this in detail, is, I am told, quite accessible/readable, and can be found at [17].

There was more to follow from Arvind, on connecting Galois field theory with the question of whether a polynomial is solvable by radicals (i.e. by a circuit with $+$, $\times$ and radical $x^{1/n}$ gates.) Landau and Miller showed that if this question is poly-time decidable, then there is an effective poly-time construction of the required circuit as well. However I must confess to having lost out on this part, being satiated and saturated with the isomorphism algorithm.

Incidentally, the tower of groups construction used in the GI algorithm, with sifting down the cosets to obtain the desired representation, has a fascinating history involving breaking the Iron Curtain; see Babai's article in Calude's book [9].