Mathematics
Graph Isomorphism and the Graph Isomorphism Problem
Quick fact
The graph isomorphism problem is famously neither known to be solvable in polynomial time nor known to be NP-complete, making it one of the few natural problems with this ambiguous status.
Why this is interesting
You’ve probably seen a graph redrawn with different labels and wondered if it’s really the same graph. How can we tell if two graphs are the same shape?
Read the full explanation
Understanding Graph Isomorphism and the Graph Isomorphism Problem
Imagine you have a map of friendships among a group of people. If you rename every person, the map still shows the same connections. Two graphs are isomorphic if you can relabel the vertices of one graph to match the other exactly, preserving which vertices are connected. This is like having two plastic toy networks: you can bend and stretch one into the shape of the other without cutting or gluing. The labels on the vertices are irrelevant; only the pattern of edges matters. For example, a triangle drawn with vertices A, B, C is isomorphic to a triangle with vertices X, Y, Z because you can map A→X, B→Y, C→Z. Isomorphism is the mathematical way of saying two graphs are structurally identical.
A deeper explanation
To check if two graphs are isomorphic, we need a bijection f between their vertex sets such that there is an edge between u and v in one graph if and only if there is an edge between f(u) and f(v) in the other. This mapping preserves all connectivity information. Deciding whether such a mapping exists is the graph isomorphism problem. No polynomial-time algorithm is known, and yet no one has proven it is NP-complete. It sits in a curious zone, leading to theories like the existence of problems of intermediate complexity if P ≠ NP. Practically, graph isomorphism arises in chemistry (comparing molecular structures), in network analysis, and even in image recognition. Efficient algorithms exist for many special classes of graphs, and recent breakthroughs have achieved quasi-polynomial time for the general case, but the fundamental complexity remains open.