I'm a graph just like you

January 24, 2016 6:19 AM

[In late 2015], László Babai, of the University of Chicago, announced that he had come up with a new algorithm for the “graph isomorphism” problem, one of the most tantalizing mysteries in computer science.
posted by Wolfdog (22 comments total)

Babai speculated in his first talk that the problem may lie just outside its borders, in the suburbs rather than the city center. That would be the most interesting possibility, Trevisan said, since it would make graph isomorphism the first natural problem to have a quasi-polynomial algorithm but no polynomial algorithm

in the past, when quasi-polynomial solutions are found, and then, later, polynomial ones, is there any kind of pattern about how you make the leap? not necessarily something formal (well, necessarily not something formal, since otherwise people would never stop at quasi-polynomial), but a kind of general "kind of change in how you look at the problem"?

if not, then what's the motivation for suggesting this will not be polynomial?

(i thought for a moment this was a dupe, but i guess maybe it was reddit. his lectures are actually pretty good - by which i mean even if you don't understand everything, he gives you a vague intuition).
posted by andrewcooke at 6:28 AM on January 24, 2016 [1 favorite]

The result has been mentioned previously in comments on MetaFilter.
posted by Wolfdog at 6:31 AM on January 24, 2016

The article mentions that other problems with the same level of universality seem to not be polynomial, and so the intuition of solvers is that the graph isomorphism problem will probably also be hard.

p.s.The recent In Our Time podcast on P vs NP is good, and helped me finally get the distinction, and understand its importance.
posted by Wulfhere at 6:43 AM on January 24, 2016 [5 favorites]

That was some really good science writing there.
posted by Ickster at 7:13 AM on January 24, 2016

[Not being in P] would make graph isomorphism the first natural problem to have a quasi-polynomial algorithm but no polynomial algorithm. “It would show that the landscape of complexity theory is much richer than we thought,” he said. If this is indeed the case, however, don’t expect a proof anytime soon: Proving it would amount to solving the P versus NP problem, since it would mean that graph isomorphism separates the problems in P from the NP-complete problems.
posted by Obscure Reference at 7:15 AM on January 24, 2016

Wulfhere and Obscure Reference - if you are answering my question, then i think you've both misunderstood either me or the entire article, although it is always possible i am mis-understanding you or your intentions.

in particular, if graph isomorphism is in P then the world will not end. it will not mean P = NP. from here:

Am I correct in assuming that even if GI was in fact contained in P, the “only” complexity theoretic implication would be to strike it (and problems that reduce to it) from the list of NPI candidates? i.e. it wouldn’t imply anything new about complexity classes.

Yes, that’s completely right, and it’s one of the basic reasons why many of us conjectured GI might be in P (another big reason being the extreme difficulty of finding hard instances in practice).

so there is no particular reason to think this will remain outside P. yet people are suggesting that. my question was: why?
posted by andrewcooke at 7:25 AM on January 24, 2016

So long as the FPP link's narrative is true to the proposed algorithm, it utilizes a similar strategy to another recent potential breakthrough in algorithms, specifically in MCMC methods. Where the FPP link describes kind of a classification scheme, the one I mention here is described as a "Shrinking Bull's-eye" on local convergence points (paper on arXiv).

Anywho, excellent Sunday morning reading, thanks for posting!
posted by JoeXIII007 at 7:51 AM on January 24, 2016 [1 favorite]

As a non-mathematician, I like graph isomorphism. A lot of graph theory quickly transcends into those realms of abstraction so cognitively encrypted they might as well be in rot13'd Sanskrit, This you can get stuck into with paper and pencil, and independently rediscover things about transformations and encoding that help build understanding of other areas of maths.

It's a really good example of 'how hard can it be?' that gently leads you into 'Oh...' territory. I wish I'd encountered exercises in mathematical thinking like this at school.
posted by Devonian at 7:58 AM on January 24, 2016 [5 favorites]

A lot of graph theory quickly transcends into those realms of abstraction so cognitively encrypted they might as well be in rot13'd Sanskrit,

Thank you for expressing it so concisely.
posted by mikelieman at 8:02 AM on January 24, 2016

Not to be a cold blanket in terms of practicality the professor did himself point out (although I'm unlikely to find the reference, perhaps Aaronson's?) that there were unlikely to be practical implications as current heuristic/approximation approaches to the problem were good and would probably always be faster than the theoretically correct algorithm.
posted by sammyo at 8:47 AM on January 24, 2016

I love the animation of the Petersen graph that the article started with. (Because of course, they have to include a picture of the Petersen graph. It's required in any discussion of graph theory, right?)
posted by leahwrenn at 9:08 AM on January 24, 2016

You can tell he's been living with this problem for a long time:

In the first of several talks on his new algorithm, on November 10, Babai called these Johnson graphs “a source of just unspeakable misery”...

posted by benito.strauss at 9:13 AM on January 24, 2016 [5 favorites]

> ... It's required in any discussion of graph theory, right?

Apparently that's not only true, it's tweetworthy.
posted by benito.strauss at 9:17 AM on January 24, 2016

László Babai is an inspiration. What a good life it must be to keep an active mind throughout the whole span of one's days on earth -- he's been working on graph isomorphism (among other things) for 40 years! He's no spring chicken. It is my ambition to age like him. Note that this is a single-authored paper; he is not just giving encouragement and guiding advice to a young mathematician who did the "grunt work". Hardy said mathematics is a young man's game. Wrong in so many ways. László Babai is an inspiration.

For those of you who don't know him, Laci is an inspiration in other ways. Back in the mid 1980's he set up the Budapest Semesters in Mathematics program, an opportunity for college kids to experience both a foreign country and the excitement of intensely delving into mathematics with a cohort of similarly intense students. I participated in its fifth year (at Laci's urging -- I was at the U of C) and it was a very influential interlude in my life. Surely he made a difference to the lives of many. Thanks, Laci!

From my few brief interactions with him, my impression is also of a very warm, endearing, and humble person. Another example to follow.
posted by brambleboy at 10:20 AM on January 24, 2016 [14 favorites]

so there is no particular reason to think this will remain outside P. yet people are suggesting that. my question was: why?

Well, nobody really knows for sure, and people's intuitions can often be wrong. That said, Babai has been thinking about this problem for about 40 years and is likely familiar with all the algorithmic tricks that could be used to improve the running time. So that's probably where his pessimism is coming from. My understanding is that the overall algorithm is divide-and-conquer on several levels. Babai even noted that he's just reusing Luks' subexponential-time (approximately O(2 ^ sqrt(n))) divide-and-conquer solution for most parts because it's actually polynomial-time for the parts that he cares about, the main interesting new part is how he deals with Johnson graphs, and my understanding is that the really tricky part was proving that Johnson graphs are the only problematic ones. So it seems that he doesn't see any better ways of handling Johnson graphs.

Earlier you asked if there was some relatively easy way of getting from quasi-polynomial time to P in general. In general the answer is no, I think. Two sort of similar (complexity-wise) problems are linear programming and primality testing. With both of those, better algorithms have repeatedly been found but I don't see anything connecting the improvements. This isn't to say that GI isn't in P, if anything my suspicion is that there is some new way of looking at things that is totally non-obvious to everyone currently working on the problem that would put it there. But the improvements found thus far have been specific to the GI problem and if there were some way of reusing algorithmic techniques or mathematical results used for better algorithms for other problems, it would be extremely interesting (and thus fairly unlikely).

Just to give a flavor of the basic solution known for many years:
0. Do the two graphs have the same number of vertices and edges? If not, return false.
1. For each set of vertices that has the same valence (number of edges), do the set sizes match between the two graphs? For instance, if graph A has 7 vertices that each have 3 edges, does graph B have 7 vertices with 3 edges? And so on. If not, return false.

The brute force algorithm (which usually works fine) is roughly to pick a mapping from each set of same-valence vertices of one graph into the corresponding set of same-valence vertices in the other graph and then test if the mapping is an isomorphism. If not, try again with different mappings. In the worst case, you have n! mappings to test, which of course is exponential in size.

The group theory involved is to take both graphs and treat them as a single graph (with no edges between the two input graphs), and find the automorphism group of the graph. An automorphism is a mapping from the set of vertices to itself that maybe maps vertices to other vertices while preserving edges. Such a function is one-to-one and onto, and thus a permutation, so the set of them form a group. If there is some permutation in the automorphism group that maps the subgraph that was originally one of the input graphs to the other subgraph (that was the other input graph), that is an isomorphism. There may be many such permutations. Once you have the automorphism group of a graph, you can find such permutations fairly easily.

So the problem turns into finding the automorphism group. It turns out that for many types of graphs, it is possible to build up permutations that form the automorphism group in polynomial time. But when you have a bunch of nodes with the same valence and a lot of edges between them, like with Johnson graphs, there are tons of possibilities that need to be tried out which until now couldn't be done in even quasi-polynomial time. Props to Babai for finding a way to solve that problem.

I studied this, and some related problems, for longer than I like to remember.
posted by A dead Quaker at 10:44 AM on January 24, 2016 [26 favorites]

[thanks. awesome reply!]
posted by andrewcooke at 10:57 AM on January 24, 2016

I'm so happy someone posted this!

From my few brief interactions with him, my impression is also of a very warm, endearing, and humble person. Another example to follow.

This past summer, I asked Laci if he had any suggestions for what to do in Hungary, as my boyfriend and I were going to be in Eastern Europe in the autumn. He realized that he was going to be in Budapest while we were in Europe, and ended up showing us around the city for a couple of days--taking us to restaurants, historical attractions, different neighborhoods, etc. (all the time quizzing us with the sort of puzzle problems that he loves...).

He was so so generous with his time. (And then a couple of months later he announces, like, the biggest result of his career!)

If you have any inclination towards math or CS, I recommend watching the seminars in which he announced the result. He's a very talented lecturer.
posted by bergamot and vetiver at 12:19 PM on January 24, 2016 [4 favorites]

The enlistment of Merlin to take the place of an oracle puts me right off.
Do they teach it this way in this century, or in Europe or Asia, or is this artistic license in the article?
posted by the Real Dan at 1:20 PM on January 24, 2016

It's a standard phrase in complexity theory.
posted by Wolfdog at 1:28 PM on January 24, 2016 [3 favorites]

Great comment, dead Quaker. I'd flag it for sidebarring if MeFi skewed a bit tech-ier.

Some question, if you don't mind remembering more: I'd have thought the automorphism group (of the combined graph) would be much harder to deal with than the original problem. Do you get a direct handle on it, say with generators and relations, or do you just prove things about it? I also can't tell if you did this in the abstract, or were actually implementing the algorithm (or is 'heuristic' a better term here?) you described.
posted by benito.strauss at 1:31 PM on January 24, 2016

It's a really good example of 'how hard can it be?' that gently leads you into 'Oh...' territory.

You are so right. I've been sitting here half an hour, and every time I think "but that's really simple, you just...", I get two sentences into writing out my "solution" and go "Oh..."
posted by Leon at 5:56 PM on January 24, 2016

every time I think "but that's really simple, you just...", I get two sentences into writing out my "solution" and go "Oh..."

The strong perfect graph conjecture did that to me for a lot longer than half an hour (back when it was still a conjecture).
posted by Wolfdog at 5:58 PM on January 24, 2016