In graph theory, graph isomorphism refers to a bijective mapping between the vertex sets of two graphs that preserves adjacency and non-adjacency relations, determining whether the graphs are structurally identical despite potentially different vertex labels.^[1] This equivalence captures the intrinsic connectivity of graphs, ignoring superficial differences in labeling or presentation, and forms a cornerstone of structural graph analysis.^[2] The graph isomorphism problem (GI) involves deciding, given two finite undirected graphs, whether such a mapping exists, a decision problem that has intrigued mathematicians since its early appearances in chemical structure comparisons during the 1950s.^[2] GI holds a unique position in computational complexity theory: it is known to be in the complexity class NP, as a proposed isomorphism can be verified in polynomial time, yet it remains neither proven to be in P nor NP-complete, placing it potentially in the class of NP-intermediate problems.^[2] A landmark breakthrough came in 2015 when László Babai announced a quasipolynomial-time algorithm, running in time $n^{(\log n)^{O(1)}}$, which improved upon prior subexponential bounds and resolved a long-standing open question, though the proof was later refined and the general case remains practically challenging for large graphs.^[3] Algorithmic approaches to GI include combinatorial methods like the Weisfeiler-Leman (WL) procedure, which refines vertex colorings to detect non-isomorphisms efficiently in many cases, and group-theoretic techniques that exploit symmetries via the automorphism group of the graph.^[2] Practical tools such as Brendan McKay's Nauty software, developed in 1981, implement these ideas and remain state-of-the-art for real-world instances, often solving problems with thousands of vertices in seconds.^[2] Beyond theory, GI has broad applications across disciplines: in chemistry for identifying molecular structures from graph representations of atoms and bonds; in computer vision for matching image patterns; in database query optimization for detecting duplicate schemas; and in machine learning for graph neural networks that rely on canonical labeling to handle isomorphic inputs invariantly.^[2] Special cases, such as isomorphism for trees or bounded-degree graphs, admit polynomial-time solutions, as shown by algorithms like those of Hopcroft and Tarjan for planar graphs in 1972, highlighting how graph properties can simplify the general problem.^[2] Ongoing research continues to explore connections to quantum computing and approximation techniques, underscoring GI's enduring relevance in both pure mathematics and applied sciences.^[4]

Fundamentals

Definition

In graph theory, two simple undirected graphs $ G = (V, E) $ and $ H = (W, F) $ are isomorphic if there exists a bijection $ \phi: V \to W $ such that for every pair of vertices $ u, v \in V $, the edge $ (u, v) $ is in $ E $ if and only if the edge $ (\phi(u), \phi(v)) $ is in $ F $.^[5] This bijection, often denoted by $ \sigma $, ensures that the structural properties of adjacency and non-adjacency are preserved exactly, meaning $ G $ and $ H $ represent the same graph up to relabeling of vertices.^[6] The relation of isomorphism between two graphs is denoted by $ G \cong H $.^[1] This preservation implies that isomorphic graphs have identical adjacency matrices up to permutation of rows and columns. Specifically, if $ A_G $ and $ A_H $ are the adjacency matrices of $ G $ and $ H $, respectively, then there exists a permutation matrix $ P $ such that $ P^T A_G P = A_H $, reflecting the vertex relabeling induced by $ \phi $.^[7] Thus, isomorphism captures an equivalence where the graphs are structurally indistinguishable, regardless of how vertices are named or positioned. A simple example of isomorphic graphs is the cycle graph $ C_4 $, which consists of four vertices connected in a closed loop, and a square graph, which is the same structure visualized as the boundary of a square; a bijection mapping the vertices sequentially around the cycle to the square's corners establishes the isomorphism.^[6] In contrast, the path graph $ P_n $ (a chain of $ n $ vertices) and the cycle graph $ C_n $ for $ n \geq 3 $ are not isomorphic, as $ P_n $ has two vertices of degree 1 while all vertices in $ C_n $ have degree 2.^[5] Graph automorphisms arise as special cases of isomorphisms where a graph is mapped to itself.^[5]

Basic Properties

Graph isomorphisms preserve numerous structural features of graphs, referred to as invariants, which remain unchanged under relabeling of vertices while maintaining adjacency relations. These invariants provide essential tools for analyzing and comparing graphs, as isomorphic graphs must share identical values for all such properties. Among the simplest invariants are the number of vertices, denoted $|V(G)|$, and the number of edges, denoted $|E(G)|$, both of which are directly preserved by any bijective mapping that maintains edges. The degree sequence, consisting of the multiset of degrees of all vertices (typically sorted in non-increasing order), is another fundamental invariant, as the bijection maps vertices to vertices of equal degree. Additional key invariants include the girth, the length of the shortest cycle in the graph (infinite if acyclic); the chromatic number, the smallest number of colors required for a proper vertex coloring; and the spectrum, the multiset of eigenvalues of the adjacency matrix. The spectrum is invariant because an isomorphism corresponds to a similarity transformation of the matrix via a permutation, which does not alter its eigenvalues.^[8][9] Isomorphisms also preserve broader structural properties such as connectedness, ensuring that paths between vertices exist or fail equivalently in mapped graphs; planarity, allowing embeddings without crossings to be correspondingly transformed; and treewidth, a measure of the graph's deviation from tree-likeness defined via decompositions into bags of bounded size, which the bijection respects. In contrast, properties like specific vertex labels or the geometric positions of vertices in a particular drawing are not invariants, as these depend on arbitrary choices external to the abstract structure.^[8][10][11] While invariants are powerful, they are not always complete for distinguishing graphs. For instance, the degree sequence alone does not determine isomorphism: there exist two non-isomorphic trees on 6 vertices, both with degree sequence (3, 2, 2, 1, 1, 1) (sorted non-increasingly). One features a central vertex of degree 3 connected to three paths of lengths 1, 1, and 3, while the other has the degree-3 vertex connected to paths of lengths 2, 2, and 1.

Variations

Labeled Graphs

In graph theory, a labeled graph extends the standard notion by assigning labels from some alphabet to its vertices, edges, or both. A labeled graph isomorphism between two such graphs $G = (V, E, \ell_V, \ell_E)$ and $H = (W, F, m_V, m_E)$, where $\ell_V: V \to \Sigma_V$ and $\ell_E: E \to \Sigma_E$ are labeling functions for vertices and edges of $G$ (with analogous functions for $H$), is a bijection $\phi: V \to W$ that preserves adjacency—i.e., $(u, v) \in E$ if and only if $(\phi(u), \phi(v)) \in F$—and also preserves labels, meaning $\ell_V(u) = m_V(\phi(u))$ for all $u \in V$ and $\ell_E(u, v) = m_E(\phi(u), \phi(v))$ for all $(u, v) \in E$.^[12][13] This requirement ensures that the structural mapping respects the additional information encoded in the labels, making the bijection more constrained than in the unlabeled case. Labeled graphs come in two primary types based on where the labels are applied. Vertex-labeled graphs assign labels only to vertices, often representing entities with inherent attributes such as identifiers or categories from a finite or infinite set. Edge-labeled graphs, in contrast, assign labels to edges, which can model relationships with properties like capacities or types; weighted graphs are a common subclass where edge labels are numerical values indicating weights.^[12][14] In both types, the isomorphism must map elements to those with identical labels, distinguishing them from unlabeled graphs where such preservation is unnecessary. For example, consider two rooted trees with identical underlying unlabeled structures but different labels on their roots. If the root of the first tree has label $a$ and the root of the second has label $b$ where $a \neq b$, no isomorphism exists between them, as any valid bijection must map roots to roots while preserving labels.^[15] This illustrates how labels can render graphs non-isomorphic even when their adjacency relations match perfectly. The condition of label preservation makes labeled graph isomorphism stricter than unlabeled graph isomorphism: every labeled isomorphism induces a valid unlabeled isomorphism by ignoring the labels, but the converse does not hold, as mappings that shuffle labels would fail the labeled criterion.^[12][14] Basic invariants from unlabeled graphs, such as the number of vertices or degree sequences, remain applicable but are supplemented by label multisets to further distinguish non-isomorphic labeled graphs.^[5]

Colored Graphs

In graph theory, a colored graph is one where each vertex or edge is assigned a color from a finite set, and an isomorphism between two such graphs is a bijection between their vertex sets that preserves both adjacency and the colors assigned to corresponding vertices and edges.^[3] This color-preserving requirement ensures that the structural and coloring properties are maintained under the mapping.^[3] Unlike proper colorings, which restrict adjacent vertices or edges from sharing the same color as in chromatic graph theory, colorings in the context of graph isomorphism are arbitrary assignments without such adjacency constraints.^[16] These arbitrary colorings partition the vertices or edges into equivalence classes based on color, where vertices or edges of the same color are indistinguishable except by their connections.^[3] This setup aligns with labeled graphs, where colors act as labels from a finite alphabet; repetitions are allowed, with multiple elements sharing a color forming a color class that permits permutations within it under isomorphism. Cases with unique labels per element correspond to singleton color classes.^[17][18] The Weisfeiler-Lehman method employs color refinement, iteratively assigning and updating colors to vertices based on their neighborhood structures, to help distinguish non-isomorphic graphs by revealing differences in these color partitions.^[19]

Motivation and Applications

Theoretical Role

Graph isomorphism serves as a cornerstone in the theoretical foundations of graph theory, enabling the classification of graphs based on their intrinsic structure rather than arbitrary labelings. By defining equivalence classes where two graphs are considered the same if there exists a bijection preserving adjacency, isomorphism facilitates the partitioning of all possible graphs into distinct structural types. This partition is crucial for enumerative purposes, as it allows mathematicians to count the number of unique graph configurations up to relabeling, avoiding overcounting due to symmetric representations. For instance, the degree sequence provides a basic invariant that remains unchanged under isomorphism, offering an initial tool for distinguishing broad classes of graphs. The historical development of graph isomorphism underscores its theoretical significance. The concept gained prominence with James Joseph Sylvester's introduction of the term "graph" in 1878, motivated by analogies to algebraic forms in chemistry, where structural equivalence was key to modeling molecular configurations. Building on this, Arthur Cayley in 1889 enumerated the number of distinct trees on labeled vertices, implicitly relying on isomorphism to identify structurally identical forms and establishing a foundational result in combinatorial enumeration. These early contributions highlighted how isomorphism bridges combinatorial counting with structural analysis. Deep connections to group theory further illuminate the theoretical role of graph isomorphism. The automorphism group of a graph, consisting of all isomorphisms from the graph to itself, captures its symmetries, while the symmetric group acts on the set of all graphs, with orbits corresponding precisely to isomorphism classes. The orbit-stabilizer theorem quantifies this action: for a graph $G$, the size of its automorphism group equals the order of the stabilizer times the size of its orbit under the symmetric group, aiding in the computation of class representatives. This framework, formalized through tools like Burnside's lemma, enables systematic enumeration of non-isomorphic objects by averaging fixed points over group elements. A persistent theoretical gap concerns the absence of a complete invariant for general graphs that unequivocally determines isomorphism classes. While invariants such as the spectrum or chromatic polynomial provide partial discrimination, no single algebraic or combinatorial invariant suffices to distinguish all non-isomorphic pairs, as demonstrated by counterexamples like non-isomorphic graphs sharing identical degree sequences and other basic properties. This limitation underscores the subtlety of structural equivalence and motivates ongoing research into refined classification methods.

Practical Uses

In chemistry, graph isomorphism plays a crucial role in canonizing molecular structures to ensure unique representations for comparison, such as generating canonical SMILES strings that resolve the graph isomorphism problem by producing identical outputs for isomorphic molecules.^[20] This approach facilitates the identification of identical compounds despite varying notations, with labeled graphs often representing atoms and bonds to capture molecular topologies.^[21] For instance, in the PubChem database, canonical SMILES and subgraph isomorphism are employed during structure standardization to detect duplicates and normalize functional groups, reducing over 53 million pre-standardized entries by 14.5% to eliminate redundant or invalid representations.^[22] In databases, graph isomorphism underpins matching operations for query optimization, particularly in RDF data where subgraph isomorphism aligns query patterns with stored triples to retrieve relevant results efficiently.^[23] This is vital for Semantic Web applications, enabling precise pattern matching in large-scale knowledge bases. Similarly, in social networks, isomorphism testing supports graph matching to identify structural similarities, such as common subgraphs representing user interactions or community patterns.^[24] In computer vision, graph isomorphism is applied to match image patterns and recognize objects by representing scenes or features as graphs and determining structural equivalence, aiding tasks like stereo vision and 3D reconstruction.^[25] In machine learning, particularly graph neural networks, techniques like the Graph Isomorphism Network (GIN) use isomorphism-aware methods to ensure invariant processing of isomorphic graphs, improving representation learning for tasks such as molecular property prediction and network analysis.^[26] In VLSI design, variants of subgraph isomorphism are applied for circuit equivalence checking, where graphs model netlists to verify that two designs share identical topologies, isolating differences for targeted refinement.^[27] This method enhances verification by matching large isomorphic subgraphs through simulation signatures and structural analysis, achieving high node match rates in practical circuits. A key challenge in these applications, especially bioinformatics involving large protein interaction or genomic networks, is scalability, as exact graph isomorphism becomes computationally prohibitive for graphs with millions of vertices, often necessitating approximate or parallel techniques to handle real-world data volumes.^[28]

Key Theorems

Whitney's Theorem

Whitney's theorem addresses the relationship between isomorphisms of graphs and their line graphs, establishing a precise correspondence under certain conditions. Specifically, for connected graphs $G$ and $H$ that are not isomorphic to $K_2$, if $G \cong H$, then every isomorphism $\phi: L(G) \to L(H)$ is induced by a unique edge bijection between $G$ and $H$, which in turn extends to a unique vertex bijection preserving the graph structure.^[29] This means that the isomorphism $\phi$ on the line graphs uniquely determines the underlying edge mapping that respects incidence relations, ensuring no extraneous symmetries in the line graphs beyond those of the original graphs. The proof relies on the definition of line graphs, where vertices represent edges of the original graph, and adjacency in $L(G)$ captures shared vertices in $G$. Given an isomorphism $\phi: L(G) \to L(H)$, it preserves this adjacency, thus inducing a bijection on edges that maintains whether pairs of edges are incident. For connected graphs excluding $K_2$, connectivity allows reconstruction of vertices as equivalence classes of incident edges (the "stars" at each vertex). The bijection on edges then uniquely maps these stars, yielding a unique vertex bijection. This uses the assumption of connectivity to avoid ambiguities in component identification and excludes $K_2$ because its line graph $L(K_2)$ is a single isolated vertex, where the trivial $\phi$ extends to two possible vertex bijections (swapping the endpoints), violating uniqueness.^[29] The theorem does not hold for disconnected graphs, as isomorphisms of line graphs may permute components with identical line graphs without corresponding to a graph isomorphism. For example, disjoint unions of isomorphic components can have line graph isomorphisms that rearrange components arbitrarily.^[30] A key corollary is that, for connected graphs $G$ and $H$, if $L(G) \cong L(H)$, then $G \cong H$, except for the pair $K_3$ and $K_{1,3}$, whose line graphs are isomorphic but the graphs are not.^[29] This result underscores the stability of line graphs in preserving structural information. The theorem was proved by Hassler Whitney in 1932 as part of his work on graph congruences and connectivity.^[29]

Stability Theorems

Stability theorems in graph isomorphism extend the foundational ideas of Whitney's theorem, which establishes that the line graph isomorphism of connected graphs generally implies the isomorphism of the originals, to broader classes of graphs and transformations. These extensions explore under what conditions derived structures, such as line graphs of multi-graphs or line digraphs, uniquely determine the original graph up to isomorphism, with identified exceptions that highlight limitations of the mapping. Such theorems are crucial for understanding when transformations preserve or reveal the underlying graph structure. Generalizations of Whitney's theorem have been developed for multi-graphs, where multiple edges between vertices are allowed. In this setting, the line graph is defined such that vertices correspond to edges of the multi-graph, and adjacency occurs if the edges share at least one vertex (or exactly one in the 1-line graph variant). A 2021 result proves that connected multi-graphs are uniquely determined by their 1-line graphs except in cases involving exactly four vertices, where a specific exception arises; for the standard line graph (adjacency if sharing at least one vertex), uniqueness holds unless the multi-graph contains a particular forbidden subgraph Δ₀. These generalizations maintain the spirit of Whitney's theorem but account for the added complexity of multiple edges, providing algorithms to recover the root multi-graph in linear time.^[31] For directed graphs, line digraphs offer a natural analogue, where vertices represent arcs of the original digraph, and an arc exists between two vertices if the head of the first arc is the tail of the second. A theorem states that for any digraph D with at least one arc, there is a unique fundamental digraph F (with sources and sinks of degree 1 and no isolated vertices) such that the line digraph of F is isomorphic to that of D. Moreover, if every vertex in two digraphs has positive in-degree and out-degree, or if the digraphs are strongly connected, then isomorphism of their line digraphs implies isomorphism of the originals. Exceptions exist for certain digraphs with non-juncture vertices, where line digraphs are isomorphic but the originals differ structurally.^[32] Similar stability results apply to rooted trees, where the line graph isomorphism, combined with root identification (often via pendant edges or degree sequences in the derived structure), preserves the rooted isomorphism. For trees in general, Whitney's theorem applies without exceptions, as trees avoid the K₃ and K_{1,3} cases, ensuring unique reconstruction. In directed settings, oriented trees (arborescences) extend this, with line digraph isomorphisms implying rooted directed isomorphism under conditions of unique paths from the root.^[33] The Behzad-Vizing conjecture from 1967–1968 addresses related aspects of line graph isomorphisms in the context of multigraph roots, positing conditions under which line graphs uniquely determine their originating multigraphs up to isomorphism, influencing later generalizations that identify exceptions for small multigraphs. This conjecture spurred research into the number of possible root graphs for a given line graph, revealing that while most line graphs have unique roots, some admit multiple non-isomorphic multigraphs as preimages.^[34] Stability under subdivision examines when isomorphism of subdivided graphs implies unique isomorphism of the originals. The subdivision S(G) of a graph G replaces each edge with a path of length 2 by inserting a degree-2 vertex. Isomorphism of S(G) and S(H) uniquely determines that G and H are isomorphic, as the original vertices correspond to non-degree-2 vertices in the subdivision, and edges to the unique paths of length 2 between them; this reconstruction is canonical and holds without exceptions for connected graphs, allowing direct recovery of the original structure. However, if subdivisions are non-uniform (different numbers of subdivisions per edge), stability may fail unless the subdivision degrees are preserved in the isomorphism. These stability theorems have significant implications for reconstructing original graphs from derived structures. In line graph contexts, algorithms based on these results enable recovery of root graphs or multigraphs from their line representations, useful in network analysis and combinatorial reconstruction problems. For subdivisions, the unique mapping facilitates topological invariants in planar graph testing and minor-closed families. Overall, such theorems provide tools for inverse problems in graph theory, ensuring that transformations like line graphs or subdivisions serve as faithful encodings for isomorphism testing and structure recovery.

Computational Complexity

Problem Formulation

The graph isomorphism problem (GI) is the decision problem of determining whether two given finite undirected graphs $G$ and $H$ are isomorphic, meaning there exists a bijection between their vertex sets that preserves adjacency relations.^[2][35] This formulation asks solely for a yes/no answer regarding the existence of such a bijection, without requiring its explicit construction.^[36] A related search variant of the problem seeks to find an explicit isomorphism, if one exists, typically represented as a permutation of the vertices of $G$ that maps it to $H$.^[37] The input graphs are commonly encoded using adjacency matrices, where the $(i,j)$-entry indicates the presence of an edge between vertices $i$ and $j$, or adjacency lists that specify the neighbors of each vertex.^[38] In the search variant, the output can be provided as a permutation matrix $P$ such that $P A_G P^T = A_H$, where $A_G$ and $A_H$ are the adjacency matrices of $G$ and $H$, respectively.^[37] Closely related is the graph automorphism problem (GA), which determines whether a single graph has a non-trivial self-isomorphism, i.e., a bijection from its vertices to themselves that preserves adjacency but is not the identity mapping.^[38] Another variant, subgraph isomorphism, asks whether one graph is isomorphic to an induced subgraph of another and is known to be NP-complete, in contrast to the unknown complexity status of GI.^[39] The recognition of graph isomorphism as a distinct computational problem dates to a 1977 survey by Read and Corneil, which highlighted its practical and theoretical challenges.^[36]

Complexity Classifications

The graph isomorphism problem (GI) is contained in NP, as an isomorphism certificate—a bijection between the vertex sets—can be verified in polynomial time by confirming that adjacency is preserved under the mapping.^[40] It also lies in co-AM, via an Arthur-Merlin protocol for graph non-isomorphism in which the prover commits to a purported isomorphism and responds to verifier challenges on random vertex permutations to demonstrate inconsistency if the graphs differ.^[40] Although in NP, GI is not known to be NP-complete; a proof of NP-completeness would imply the collapse of the polynomial hierarchy to the second level, a consequence widely believed to be false.^[40] In a major breakthrough, László Babai developed a quasi-polynomial time algorithm for GI in 2015, achieving runtime $\exp(O((\log n)^c))$ for some constant $c > 1$, which places the problem in quasi-PTIME; the result was initially retracted due to an error but confirmed in revised form by 2017 after extensive verification.^[41][42] This algorithm relies on group-theoretic techniques, including local certificates for permutation group actions, and simultaneously resolves string isomorphism under group action (SI) in quasi-polynomial time, establishing that GI and SI have equivalent computational complexity.^[40] The graph automorphism problem (GA) is polynomial-time many-one reducible to GI, meaning that solving GI in polynomial time would imply the same for GA, though the converse reduction remains open.^[2] Certain restricted classes admit polynomial-time solutions: GI for trees can be tested in linear time using bottom-up subtree matching, while for planar graphs, polynomial-time algorithms exist based on decomposition into 3-connected components and canonical forms.^[40][43] Additionally, graphs of bounded maximum degree $d$ are solvable in polynomial time via group-theoretic reductions to the color automorphism problem, as shown by Luks in 1982, with runtime $n^{O(d / \log d)}$.^[44] No polynomial-time algorithm for general GI is known as of 2025, and the problem's hardness stems from group-theoretic challenges, particularly the representation and decomposition of primitive permutation groups acting on large sets, which resist sub-quasi-polynomial progress under standard assumptions.^[40] Nevertheless, practical tools like nauty and Traces routinely handle instances with thousands of vertices—and up to tens of thousands in sparse cases—leveraging heuristics and canonical labeling for real-world applications.

Algorithms and Recognition

Canonical Labeling

Canonical labeling addresses the graph isomorphism problem by producing a standardized representation for each isomorphism class, enabling direct comparison of graphs. A canonical labeling assigns vertex labels to a graph $G$ such that the resulting labeled graph is isomorphic to $G$ and uniquely identifies its entire isomorphism class, often through a canonical form like an adjacency matrix that is invariant under isomorphism.^[45] This form ensures that any two isomorphic graphs receive identical labelings, distinguishing non-isomorphic ones.^[46] The method typically involves generating a canonical form by exploring possible vertex permutations and selecting one that minimizes a predefined ordering, such as the lexicographically smallest adjacency matrix when read row by row.^[47] Graph isomorphism testing then simplifies to computing these canonical forms for both input graphs and verifying their equality, effectively reducing the problem to a straightforward string or matrix comparison.^[48] This approach offers advantages in efficiency for isomorphism checks and proves valuable in graph enumeration, where it helps eliminate isomorphic duplicates from generated sets.^[49] Historically, Brendan D. McKay's nauty tool, introduced in 1981, pioneered practical canonical labeling through a partitioning and refinement strategy that refines vertex orbits to produce the unique form.^[49] For instance, in the cycle graph $C_3$ (a triangle with vertices connected in a loop), all rotations map to the same canonical adjacency matrix:

$$\begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix},$$

which serves as the unique representation for this isomorphism class.^[45]

Practical Algorithms

Practical algorithms for graph isomorphism testing typically combine heuristic pruning with exact backtracking or refinement techniques to handle moderate-sized graphs efficiently. One prominent approach is the VF2 algorithm, a backtracking method originally developed for labeled subgraph isomorphism and adapted for graph isomorphism testing. Introduced by Cordella et al., VF2 employs a depth-first search strategy that prunes the search tree using feasibility rules based on vertex labels, degrees, and adjacency invariants, making it suitable for graphs up to several thousand vertices in practice.^[50] This algorithm iteratively matches vertices while checking look-ahead conditions to avoid infeasible branches early, balancing computational cost with completeness.^[51] Partition refinement techniques, such as the 1-dimensional Weisfeiler-Lehman (1-WL) algorithm—also known as color refinement—provide an initial partitioning of vertices to reduce the search space before backtracking. In this method, vertices are iteratively colored based on their neighborhood structure, starting with initial colors from invariants like degrees, and refining colors until stabilization; graphs with differing color distributions after refinement cannot be isomorphic.^[52] The 1-WL algorithm, originating from Weisfeiler and Leman's work on graph stabilization, serves as a fast heuristic that rejects non-isomorphic pairs in linear time relative to the graph size.^[52] The Nauty/Traces software suite implements a refined version of these principles, using partition refinement combined with group-theoretic automorphism computation for exact isomorphism testing and canonical labeling. Developed by McKay and extended by Piperno, Nauty applies individualization-refinement cycles to explore the search tree efficiently, computing automorphisms as a byproduct.^[53] Traces, an extension for directed graphs, follows a similar framework but handles orientations explicitly.^[53] In practice, these algorithms perform well on graphs with 100 to 1000 vertices, leveraging invariants like degree sequences for early pruning; for instance, if two graphs have mismatched sorted degree sequences, isomorphism is immediately ruled out without further computation.^[35] VF2 and Nauty both incorporate such checks, enabling rapid rejection of non-candidates in applications like chemical structure matching or network analysis.^[51] While exact, they may require heuristics for denser or larger instances beyond this range. Canonical labeling, often produced as output by tools like Nauty, facilitates comparison by mapping graphs to a standard form.^[35]

Recent Advances

A major breakthrough in the theoretical understanding of graph isomorphism came in 2015 when László Babai announced a quasi-polynomial time algorithm for the problem, achieving a running time of $ \exp(O((\log n)^c)) $ for some constant $ c > 0 $, where $ n $ is the number of vertices. The algorithm relies on sophisticated group-theoretic methods, including local certificates for graph automorphisms and the combinatorial nullstellensatz to bound the search space in quotient graphs. This result resolved a long-standing open question by placing graph isomorphism firmly within quasi-polynomial time, though the exact constant $ c $ was initially around 5 and later refined.^[54] Following the announcement, a flaw was identified in the analysis by Harald Helfgott in early 2017, leading Babai to temporarily retract the quasi-polynomial claim and revert to a subexponential bound. Babai promptly corrected the error with a simple new lemma, restoring the quasi-polynomial time guarantee later that month.^[55] The revised proof underwent extensive peer review and was fully confirmed by 2020, solidifying its status as a landmark achievement in algorithmic group theory.^[4] Building on Babai's framework, subsequent refinements have targeted special cases, particularly graphs of bounded degree. For instance, Grohe, Neuen, and Schweitzer developed an improved isomorphism test for bounded-degree graphs in 2018, achieving a running time of $ n^{O((\log d)^c)} $ where $ d $ is the maximum degree, by enhancing the group-theoretic decomposition techniques to handle almost-group isomorphisms more efficiently. These extensions exploit the restricted structure of low-degree graphs to reduce the branching in the automorphism group computation. The impact of Babai's algorithm extends beyond graph isomorphism itself, placing the problem in the complexity class QP and providing new tools for related problems such as string isomorphism, which Babai showed is also solvable in quasi-polynomial time via similar quotient-based reductions. It has also influenced approximate counting problems in graphs, where randomized reductions to isomorphism enable quasi-polynomial solutions for estimating the number of automorphisms.^[4] Despite these advances, significant open questions remain, including whether graph isomorphism admits a true polynomial-time algorithm, as the quasi-polynomial bound leaves a substantial gap to $ P $.^[4] Furthermore, Babai's method remains highly theoretical, with no practical implementations achieving the full quasi-polynomial performance on real-world instances as of 2025 due to the immense constants and complex group computations involved.^[4] Recent work has explored parallel variants, such as massively parallel algorithms that adapt Babai's techniques to distributed models, though these are still in early stages.