Communications of the ACM
The Graph Isomorphism Problem
Credit: Getty Images
Deciding whether two graphs are structurally identical, or isomorphic, is a classical algorithmic problem that has been studied since the early days of computing. Applications span a broad field of areas ranging from chemistry (Figure 1) to computer vision. Closely related is the problem of detecting symmetries of graphs and of general combinatorial structures. Again this has many application domains, for example, combinatorial optimization, the generation of combinatorial structures, and the computation of normal forms. On the more theoretical side, the problem is of central interest in areas such as logic, algorithmic group theory, and quantum computing.
Figure 1. Nonisomorphic molecular graphs.
Key Insights
Graph isomorphism (GI) gained prominence in the theory community in the 1970s, when it emerged as one of the few natural problems in the complexity class NP that could neither be classified as being hard (NP-complete) nor shown to be solvable with an efficient algorithm (that is, a polynomial-time algorithm). It was mentioned numerous times as an open problem, in particular already in Karp's seminal 1972 paper23 on NP-completeness as well as in Garey and Johnson's influential book on computers and intractability.15 Since then, determining the precise computational complexity of GI has been regarded a major open problem in theoretical computer science.
No entries found