graphs anyone would ever care about.”
In fact, the graph isomorphism solution is similar to the Agrawal-Kayal-Saxena algorithm in that way, says
Boaz Barak, Gordon McKay professor
of Computer Science at Harvard University’s John A. Paulson School of
Engineering and Applied Sciences. “It
was a great intellectual breakthrough,
but even before it, we had highly efficient heuristics that seemed to solve
the problem.” Barak says Babai’s
paper contains several significant
new ideas that may have an effect on
mathematics and may someday lead
to practical applications in graph isomorphism or some other problem,
adding, “however, it is impossible, at
least for me, to predict this potential
impact at this point.”
Separate Spheres
Practical solutions for specific cases of
graph isomorphism have existed for
years. In a 1981 paper entitled “Prac-
tical Graph Isomorphism,” computer
scientist Brendan McKay of the Aus-
tralian National University in Canberra
developed an isomorphism testing
program called nauty (for No AUTo-
morphisms, Yes?) that is widely used
today. He describes the difference
between the theory and practice of
graph isomorphism “as being like two
galaxies that have only a few stars in
common.”McKay does not believe this
breakthrough will help close the gap
between theory and practice, a belief
he says he shares with Babai. “Nobody
knows how to apply any of Babai’s ideas
to improve the practical performance
of programs for graph isomorphism,”
McKay says. “If one just programs Ba-
bai’s algorithm on a computer without
making any changes, it will be hope-
lessly slow compared to the best cur-
rent programs.”
Faulon hopes Babai’s ideas do
eventually lead to some changes in
practice. “We are still lacking a prac-
tical polynomial-time algorithm in
chemistry,” he says.
Another person hoping the theo-
ry can be translated into practice is
Hasan Jamil, a computer scientist at
the University of Idaho’s Institute for
Bioinformatics and Evolutionary Stud-
ies. Jamil is searching for a gene that
affects the death of cells in neurologi-
cal disorders such as Alzheimer’s and
Parkinson’s diseases. Graph matching
for the cells’ regulatory networks and
protein networks could help him iso-
late such a gene or set of genes. When
he submitted a paper and the reviewers
asked for a new experiment to back up
his theory, however, the publication
process slowed to a crawl. “If I have to
find an isomorphic match, or even an
approximate match, it takes hours and
hours and months to even find simple
things,” he says. With approximately
24,000 genes in the human body, each
of them capable of producing four
or five different proteins and then of
interacting amongst themselves, the
number of possible matches quickly
becomes astronomical.
He hopes Babai’s proposed solution
leads to something better. “If it brings
down the complexity, even a bit, it
helps us search things in a reasonable
amount of time,” Jamil says.
If Babai’s work does lead to practical improvements, they may lie far in
the future. McKay says, though, that
Babai’s ideas have started him thinking about whether there might be
some useful application. “The odds
don’t look good,” McKay says, “but
just maybe there is a pleasant surprise
lurking.”
Further Reading
Babai, L.
Graph Isomorphism in Quasipolynomial
Time, arXiv, Cornell University Library, 2015,
http://arxiv.org/abs/1512.03547
McKay, B.D., and Piperno, A.
Practical Graph Isomorphism II,
Journal of Symbolic Computation, 60, 2014,
http://arxiv.org/abs/1301.1493
Fortnow, L.
The status of the P versus NP
problem, Communications of the ACM,
September 2009, http://cacm.acm.org/
magazines/2009/9/38904-the-status-of-
the-p-versus-np-problem/fulltext
Fortnow, L., and Grochow, J.A.
Complexity classes of equivalence
problems revisited, Information and
Computation, 209, 2011, http://arxiv.org/
pdf/0907.4775.pdf
Isomorphic Graphs, Example 1,
Stats-Lab Dublin
https://www.youtube.com/watch?v=Xq8o-
z1DsUA
Neil Savage is a science and technology writer based in
Lowell, MA.
© 2016 ACM 0001-0782/16/07 $15.00
there is evidence it is not NP-complete
either. The best theoretical algorithm,
published by Babai and Eugene Luks
in 1983, was sub-exponential—better
than any known algorithm for any NP-
complete problem, but still far from
easy. This new algorithm appears to
place graph isomorphism in quasi-
polynomial time, much closer to the
easy side. “This is just such a huge
theoretical improvement from what we
had before,” Fortnow says. “Now it’s
not likely at all to be NP-complete and
it’s not that hard at all.”
Josh Grochow, an Omidyar Postdoc-
toral Fellow in theoretical computer
science at the Santa Fe Institute in New
Mexico, calls Babai’s proposed solu-
tion a big theoretical jump. “There re-
ally are very few problems we know of
in this limbo state,” he says. Graph iso-
morphism is “still in the limbo state,
but it’s a lot clearer where it sits.”
In some subset of graphs, the ques-
tion was already settled. For instance,
molecular graphs have “bounded
valence,” meaning the physical con-
straints of three-dimensional space
allow atoms to be connected only to a
limited number of other atoms, says
Jean-Loup Faulon, a synthetic biologist
at the University of Manchester, Eng-
land, and INRA in France, who uses
graph matching in his work. In the
1980s, he points out, Babai, Luks, and
Christoph Hoffmann showed bound-
ed valence graphs could be solved in
polynomial time. “Therefore, the prob-
lem of graph isomorphism is already
known to be polynomial for chemi-
cals,” Faulon says.
While Babai’s work has generated
much excitement among theoreticians, experts say it is not likely to have
much effect in practice; at least, not immediately. Scott Aaronson, a computer
scientist at the Massachusetts Institute
of Technology who studies computational theory, says, “this is obviously
the greatest theoretical algorithms result” at least since 2002, when Manin-dra Agrawal, Neeraj Kayal, and Nitin
Saxena came up with an algorithm
for determining, in polynomial time,
whether a number is a prime. “On the
other hand,” Aaronson says, “the immediate practical impact on computing is zero, because we already had
graph isomorphism algorithms that
were extremely fast in practice for any