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