Skip to content

A Little More on the Graph Isomorphism Algorithm

November 21, 2015

Looking at some of its components

From source, our congrats too

Laci Babai’s first talk a week ago Tuesday is now a webcast here. There is also a great detailed description of his talk by Jeremy Kun, including background on the problem and how the proof builds on Eugene Luks’s approach.

Today we talk some more about ingredients of Laci’s algorithm.

He has one more scheduled talk this coming Tuesday on its key vehicle of progress: Either the current graph (and associated groups) in the recursion can be split up for divide-and-conquer, or it embeds a special kind of graph named for Selmer Johnson that can be handled specially. This strikes us as following another Chicago idea—the Geometric Complexity Theory programme of Ketan Mulmuley and Milind Sohoni—of looking for objects that obstruct the progress of algorithms; this post by Joshua Grochow discusses an example for matrix multiplication.

Rather than try to anticipate these further details and Laci’s forthcoming preprint, we thought we might give more high-level discussion of some more ideas and elements we recognize that make the algorithm work. We could be way off, but these ideas we believe are key to his breakthrough result. In any event they are useful insights that we hope you enjoy.

All Aboard

Laci’s talk is old style, a chalk talk. Most talks these days are powerpoint-style, but for details and complex mathematics, there is nothing like seeing a master at work using chalk. The virtues of such a talk are many. It slows down the information rate to the audience. This is good. Slow is good. Flipping powerpoint slides rapidly can be hard to follow. Watching Laci write out in his handwriting:

Graph Isomorphism  GI

is wonderful. You can follow it, internalize it, and perhaps understand it.

The second is the use of many boards. This is wonderful. It gives a larger state for the audience, so they are more likely to understand.



The key ideas of the algorithm for GI are really classic ones from design of algorithms. The genius is getting them all to work together. The ideas break into two types: those that are general methods from computer science and those that are special to the GI problem.

Domain-General Points

{\bullet } Small Steps. One of the most important principles in mathematics and also in the design of complex algorithms is that we rarely can just write down the answer. That is if we wish to construct something we rarely can just write down the answer in closed form. The quadratic formula for the roots of {ax^{2} + bx +c = 0} is a classic counterexample:

\displaystyle x = \frac{-b \pm \sqrt{b^{2}-4ac}}{2a}.

Of course there are no such formulas for high degree polynomials nor for non-polynomial equations. Enter the Newton method.

The idea of building the answer in small steps is the cornerstone of most important algorithms. Linear programming uses simplex or interior point methods, matching uses path-augmentation, and so on.

{\bullet } Recursion. The reason the small step idea is so powerful is that it plays well with running time. If the small steps can be bounded by a nice equation, then the algorithm in question will run fast. For Laci’s case the key is

\displaystyle T(n) \le q(n)T(0.9n).

where {q(n)} is a quasi-polynomial term. This type of equation yields a quasi-polynomial running time. If we had a constant {c} in place of {q(n)} then we would get a term {c^{O(\log n)}} which is polynomial, and this typifies how one gets polynomial-time algorithms by divide-and-conquer. Here {q(n)} is not constant, but quasi-polynomial terms are closed under raising them to log powers, so that is the time we get. The recursion can be cut off when the problem size is polylog.

{\bullet } This-or-That. As Laci says, “split-or-Johnson.” This is the hardest element to convey simply but may pay the highest dividends if we can recognize when it can be used. Here is an example: For every {\epsilon > 0} there exists {\delta > 0} such that for every {n}-vertex graph {G}:

Either {G} has at least {\delta n^3} triangles, or one can remove {\epsilon n^2} edges to leave no triangles.

This enables a randomized algorithm to distinguish graphs that are triangle-free from those that are {\epsilon}-far from being triangle-free: it can try (say) {3/\delta} random triples of vertices and say “probably triangle-free” if none is a triangle. The randomized primality test of Gary Miller and Michael Rabin can also be phrased as an either-or in which the “or” branch finds a factor. To be sure, Laci’s algorithm isn’t randomized.

Domain-Specific Elements

{\bullet } Graph Marking. Perhaps the main problem with GI has always been that looking locally at vertices of some graph {G} may yield no information about the graph. Locally all the neighborhoods of vertices may look alike. This is terrible from the point of view of trying to tell one vertex from another, which is critical to be able to solve the GI problem.

But there is an expensive way to change this. We simply pick a set of vertices of {G} and mark them in a unique manner. Now using these we can start to break up the structure of the graph and start to label vertices differently. Obviously a vertex near one of these marked vertices is different from one that is farther away. This is a critical “trick” that allows one to make progress on GI for the graph.

There is a cost. If we pick {t} such special vertices in a graph, then we must try all ways to pick these in the other graph. That is expensive. If the graph has {n} vertices then it costs {n \choose t}. So to avoid taking more than quasi-polynomial time, we must keep {t} of size at most poly-logarithmic. It also needs {t} of order at least {(\log n)^3} to be effective, which is a reason the technique cannot simply be improved to run in polynomial time.

{\bullet } Groups Are Nice. One of the most useful properties of groups is the “subgroup size trick.” In most structures, including graphs, a substructure can be very big. Suppose that {G} is a graph on {n} vertices. It has subgraphs with {n-1} vertices—just remove any vertex. This cannot happen with groups. If {H} is a groups with {n} elements, then the largest nontrivial subgroup can have at most {n/2}. This is a simple consequence of the famous theorem of Joseph-Louis Lagrange that for any finite group {H}, the size of every subgroup of {H} divides the size of {H}. If you keep taking subgroups and each one is proper then you quickly make great progress reducing the size.

The worst case is when the factor is {2} such as with the alternating group {A_m} inside the symmetric group {S_m}. Babai calls a homomorphism {\phi} from a group {G} into {S_m} giant if its image is either {A_m} or all of {S_m}. An element {x} of the set {G} acts on is unaffected if {\phi} restricted to the subgroup {G_x} of permutations that fix {x} is still giant. Subject to conditions about the setting that we don’t yet fully understand, his key new group-theoretic theorem is:

Unless {m} is tiny, the restriction of a giant homomorphism to the intersection of {G_u} over all unaffected elements {u} is still giant.

This looks like it should be either easily true or easily false, but Babai’s precise statement depends on the classification of finite simple groups.

The key inner point of the algorithm is to try subsets {A} of the elements where {|A|} is polylog but not tiny so the theorem works for {S_{|A|}}. The theorem helps decide in quasipolynomial time whether the resulting homomorphism into {S_{|A|}} is giant. This distinguishing power in turn is used to make progress.

Open Problems

What is the full pattern of progress in the algorithm, with “split-or-Johnson” evidently directing the outermost loop and the above the inner loops? This may need more details to unfold.

A Fast Graph Isomorphism Algorithm

November 11, 2015

While we wait for Laci {\dots}

László Babai just gave his first talk on his new graph isomorphism (GI) algorithm. The photo was taken at the talk and posted by several people.

Today we want to discuss his talk, but {\dots} Read more…

The World Series Of Complexity Theory

November 9, 2015

László’s three talks

Chicago Chronicle source

László Babai must be busy getting ready for his series of talks.

Today Ken and I wish to discuss one issue that has come up in comments about his result.

By the way, the big event this Tuesday is not the Republican Debate on Fox, but Laci’s talk. It’s too bad for Chicago that the Cubs didn’t reach this year’s World Series, but these talks will make up for it. Read more…

A Big Result On Graph Isomorphism

November 4, 2015

Jumping GI down from the nearly-exponential neighborhood to the nearly-polynomial one


László Babai is one of the world experts on complexity theory, especially related to groups and graphs. He also recently won the 2015 ACM Knuth Prize, for which we congratulate him.

Today we wish to discuss a new result that he has announced that will place graph isomorphism almost in polynomial time.
Read more…

Ghosts in Princeton

November 1, 2015

Kurt Gödel in popular culture and answers to Thursday’s problems

Levi Weaver source

Kurt Gödel may yet make it to Broadway. He already splashed across the silver screen in the 1994 Meg Ryan-Tim Robbins comedy I.Q. as the roly-poly sidekick of Walter Matthau playing Albert Einstein. He was pressed into retro vinyl by Levi Weaver for his 2011 album The Letters of Dr. Kurt Gödel. He features in the major Japanese manga series Negima! These borrowings may be incomplete or inconsistent, but with Gödel that’s par, no?

Today we consider Gödel’s impact on popular culture and give answers to the conjectures in Thursday’s post.
Read more…

Guessing Conjectures

October 29, 2015

How well can we guess the right side of yes/no questions?


Takaaki Kajita and Arthur McDonald won the 2015 Nobel Prize in Physics for their discovery that neutrinos have mass. Although some physicists had shown as early as the 1950s that standard particle models could accommodate neutrinos with mass, there was no compelling reason for it. Moreover, the most-discussed terms for neutrino mass lack the desirable mathematical property of renormalizability. So most physicists of the last century guessed that neutrinos would be massless like photons are.

Today Ken and I wish to talk about guessing the answers to problems and conjectures in mathematics.
Read more…

Rankings Versus Ratings

October 22, 2015

Handling both with the amazing generalized Kendall tau distance


Michelle Kwan was one of the last great figure skaters to compete under the historic “6.0” ranking system. She won the world championship five times under that system but was a squeaker second in the 1998 Winter Olympics and a more-distant third in 2002. An injury on the eve of the 2006 Winter Olympics prevented her from competing under the new and current system, which involves a complex numerical rating formula.

Today we discuss rankings versus ratings with an eye to complexity and managing them by common tools.
Read more…


Get every new post delivered to your Inbox.

Join 2,590 other followers