news

I M A G E F R O M W I K I M E D I A . O R G

N
Science | DOI: 10.1145/2933412 Neil Savage
Graph Matching in
Theory and Practice
A theoretical breakthrough in graph isomorphism excites
complexity experts, but will it lead to any practical improvements?

In computer science, a graph is a
network, a series of nodes strung to-
gether by connections known as edges;
the set of Facebook users and their in-
terconnections make up a graph with
approximately 1. 5 billion nodes. Two
graphs may be depicted differently,
but if the nodes and connections in
Michael Garey and David S. Johnson,
helpfully provided an appendix listing
a dozen problems not known to fit into
one category or the other.

“The very first one that’s listed is
graph isomorphism,” says Lance Fort-
now, chair of computer science at the
Georgia Institute of Technology. In the
decades since, most of the problems
on that list were slotted into one of the
two categories, but solving graph iso-
morphism—in essence figuring out if
two graphs that look different are in
fact the same—resisted categorization.
“Graph isomorphism just didn’t fall.”
Now László Babai, a professor of
computer science and mathematics
at the University of Chicago, has devel-
oped a new algorithm for the problem
that pushes it much closer to—but not
all the way into—the easy category, a
result complexity experts are hailing
as a major theoretical achievement, al-
though whether his work will have any
practical effect is unclear.

Two graphs that are isomorphic.