234. How would you test whether two graphs are isomorphic?
HardGraph algorithms
Technical
Show model answer
Two graphs are isomorphic if some bijection of vertices maps edges exactly onto edges. Brute force tries all n! bijections, O(n!·n²). No polynomial algorithm is known for general graphs, but the problem is not known to be NP-complete either; Babai's 2015 result gives quasi-polynomial time.
In practice, reject quickly using invariants that isomorphic graphs must share: vertex and edge counts, sorted degree sequences, number of components, cycle and triangle counts, and spectra. Then use backtracking with refinement (color vertices by degree and iteratively refine by neighbor colors, the Weisfeiler-Leman idea) to prune candidate mappings. Trees can be checked in linear time with canonical encodings.