Communications of the ACM
Graph Matching in Theory and Practice
Two graphs that are isomorphic.
Credit: Wikimedia.org
Back in 1979, two scientists wrote a seminal textbook on computational complexity theory, describing how some problems are hard to solve. The known algorithms for handling them grow in complexity so fast that no computer can be guaranteed to solve even moderately sized problems in the lifetime of the universe. While most problems could be deemed either relatively easy or hard for a computer to solve, a few fell into a strange nether region where they could not be classified as either. The authors, 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 Fortnow, 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 isomorphism—in essence figuring out if two graphs that look different are in fact the same—resisted categorization. "Graph isomorphism just didn't fall."
No entries found