Fact-checked by Grok 2 weeks ago

Graph isomorphism

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.

References

[1]
Isomorphic Graphs -- from Wolfram MathWorld
Two graphs which contain the same number of graph vertices connected in the same way are said to be isomorphic. Formally, two graphs and with graph vertices ...<|control11|><|separator|>
[2]
The Graph Isomorphism Problem - Communications of the ACM
Nov 1, 2020 · The problem GI of deciding whether two graphs are isomorphic and the problem of computing a generating set for the automorphism group of a graph ...
[3]
[PDF] Groups, Graphs, Algorithms: The Graph Isomorphism Problem
Feb 18, 2018 · Abstract. Graph Isomorphism (GI) is one of a small number of natural al- gorithmic problems with unsettled complexity status in the P / NP.
[4]
[2011.01366] Recent Advances on the Graph Isomorphism Problem
Nov 2, 2020 · We give an overview of recent advances on the graph isomorphism problem. Our main focus will be on Babai's quasi-polynomial time isomorphism test.
[5]
[PDF] Section 1.2. Isomorphisms and Automorphisms
May 18, 2022 · In this section we define a graph isomorphism, consider automorphisms and symmetries of a given graph, and define a labeled simple graph.
[6]
11.4: Graph Isomorphisms - Mathematics LibreTexts
Jul 12, 2021 · The answer lies in the concept of isomorphisms. Intuitively, graphs are isomorphic if they are identical except for the labels (on the vertices).
[7]
The Adjacency Matrix | An Introduction to Algebraic Graph Theory
Conversely, for any graph that is isomorphic to there exists a permutation matrix such that is the adjacency matrix of . Let be a permutation with permutation ...
[8]
[PDF] The Basics
isomorphic to G. A map taking graphs as arguments is called a graph invariant if it assigns equal values to isomorphic graphs. The number invariant of ...
[9]
[PDF] Math 443/543 Graph Theory Notes 5: Graphs as matrices, spectral ...
Nov 3, 2014 · Similarly, the permutation matrix gives an isomorphism. Now we see that the adjacency matrix can be used to count uv-walks.
[10]
https://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch4.pdf
[11]
[PDF] Treewidth
A powerful framework for efficient algorithms on planar graphs. Setup: Let x(G) be some graph invariant (i.e., an integer associated with each graph).
[12]
[PDF] Enhancements to the Perfect Matching Approach for Graph ...
Aug 16, 2020 · that generates the set of vertex-labeled graphs in the graph struc- ... Definition 1 (Labeled Graph Isomorphism). Consider two labeled ...
[13]
[PDF] arXiv:0710.2571v1 [math.GR] 13 Oct 2007
Oct 13, 2007 · If (Γ, GΓ) and (Σ, GΣ) are labeled-graphs with directly- indecomposable cyclic vertex groups and there exists a group isomor- phism φ: W(Γ) → W( ...
[14]
[PDF] arXiv:2211.05637v1 [cs.CC] 9 Nov 2022
Nov 9, 2022 · Two graphs are isomorphic iff there is a bijection between their vertices that respects adjacency and labels of vertices and edges. The graph ...<|control11|><|separator|>
[15]
[PDF] 3.1 Characterizations and Properties of Trees 3.2 Rooted Trees ...
Def 2.12. Two rooted trees are said to be isomorphic as rooted trees if there is a graph isomorphism between them that maps root to root. Example 2.4. There ...
[16]
[PDF] Graph Isomorphism, Color Refinement, and Compactness?
Automorphisms of a vertex-colored graph and isomorphisms between vertex-colored graphs are required to preserve vertex colors. We get usual graphs when c is ...
[17]
A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants - arXiv
Jan 18, 2022 · The classical Weisfeiler-Lehman algorithm (WL) -- a graph-isomorphism test based on color refinement -- became relevant to the study of graph ...
[18]
[PDF] Algorithms in Chemoinformatics Canonical Representations and ...
May 15, 2019 · ▫ Canonicalization of molecular representations allows easy identification of identical molecules. ▫ It solves the “graph isomorphism” problem.
[19]
A standard method to generate canonical SMILES based on the InChI
Sep 18, 2012 · This is the first description of a method to generate canonical SMILES that takes stereochemistry into account.Canonical Labelling · Shuffle Test · Duplicate Test
[20]
PubChem chemical structure standardization
Aug 10, 2018 · The PubChem standardization is an effective and efficient tool to account for molecular diversity and to eliminate invalid/incomplete structures.
[21]
[PDF] Taming Subgraph Isomorphism for RDF Query Processing
In this paper, based on the state-of-the-art subgraph isomorphism al- gorithm, we propose an in-memory solution, TurboHOM++, which is tamed for the RDF ...
[22]
On graph query optimization in large networks - ACM Digital Library
In this paper, we present a high performance graph indexing mechanism, SPath, to address the graph query problem on large networks.
[23]
[PDF] Incremental Sequential Equivalence Checking and Subgraph ...
A method for finding large isomorphic subgraphs in two similar circuits is proposed, and its application to sequential equivalence checking (SEC) is discussed.Missing: VLSI | Show results with:VLSI<|separator|>
[24]
SAGA: a subgraph matching tool for biological graphs | Bioinformatics
This paper presents a novel approximate graph matching technique called SAGA. This technique employs a flexible model for computing graph similarity.Missing: challenges | Show results with:challenges
[25]
Congruent Graphs and the Connectivity of Graphs - jstor
CONGRUENT GRAPHS AND THE CONNECTIVITY OF GRAPHS.*. By HASSLER WHITNEY. Introduction. We give here colnditions that two graphs be congruent and some theorems ...
[26]
[PDF] Line Graphs Math 381 — Spring 2011 Since edges are so ... - People
Theorem LG. 6 (Whitney's Theorem). If G and H are connected graphs and L(G) is iso- morphic to L(H), then G and H are isomorphic, or else G = K1,3 and H = K3. ...Missing: exact | Show results with:exact
[27]
Line graph - Wikipedia
Hassler Whitney (1932) proved that with one exceptional case the structure of a connected graph G can be recovered completely from its line graph. Many ...
[28]
[PDF] arXiv:2105.08610v1 [math.CO] 18 May 2021
May 18, 2021 · We extend Whitney's theorem to such line graphs of multi-graphs, and show that most multi-graphs are uniquely determined by their line graph.
[29]
[PDF] A Survey of Line Digraphs and Generalizations
Mar 11, 2021 · While the name line graph was introduced by Harary and Norman [15] in 1960, the concept actually originated in 1932 by Whitney [24] in his study ...
[30]
show that if two trees have isomorphic line graphs , they are ...
May 25, 2016 · I want to use Whitney isomorphism theorem: if the line graphs of two connected graphs are isomorphic, then the underlying graphs are isomorphic.Connection Between Automorphism Groups of a Graph and its Line ...How many graphs can have the same line graph?More results from math.stackexchange.com
[31]
[PDF] Whitney's Theorem for Line Graphs of Multi-Graphs
May 18, 2021 · Whitney's Theorem states that every graph, except K3 or K1,3, is uniquely determined by its line graph. This is extended to multi-graphs.
[32]
Shrikhande graph
Math. Statist. 30 (1959) 781-798, that strongly regular graphs with the parameters of a lattice graph H(2,n) are isomorphic to H(2,n), except for n = 4, where ...Missing: product | Show results with:product
[33]
Practical graph isomorphism, II - ScienceDirect.com
The graph isomorphism problem (GI) is that of determining whether there is an isomorphism between two given graphs.
[34]
The graph isomorphism disease - Read - 1977 - Wiley Online Library
This paper surveys the present state of the art of isomorphism testing, discusses its relationship to NP-completeness, and indicates some of the difficulties
[35]
[PDF] Lecture 5 1 Graph Isomorphism 2 Interactive Proofs
Graph isomorphism is proven by finding a vertex renaming (π) where edges become edges and non-edges become non-edges. Interactive proofs can be used to prove ...<|control11|><|separator|>
[36]
Graph Automorphism -- from Wolfram MathWorld
An automorphism of a graph is a graph isomorphism with itself, i.e., a mapping from the vertices of the given graph G back to vertices of G ...
[37]
[PDF] 1 Subgraph Isomorphism - Stanford CS Theory
Sep 28, 2016 · If H is part of the input, Subgraph Isomorphism is an NP-complete problem. It generalizes problems such as Clique, Independent Set, and ...
[38]
[PDF] Group, graphs, algorithms: the Graph Isomorphism Problem
Graph Isomorphism (GI) is one of a small number of natural algorithmic problems with unsettled complexity status in the P / NP theory: not expected to be NP- ...
[39]
[1512.03547] Graph Isomorphism in Quasipolynomial Time - arXiv
We show that the Graph Isomorphism (GI) problem and the related problems of String Isomorphism (under group action) (SI) and Coset Intersection (CI) can be ...Missing: confirmed 2017
[40]
[PDF] Graph Isomorphism in Quasipolynomial Time
Nov 2, 2018 · The Graph Isomorphism (GI) problem can be solved in quasipolynominal time, which is exp((log n)^O(1)), improving the previous bound of exp(O(√n ...Missing: 2024 2025
[41]
[2503.01180] Reduction of the group isomorphism problem to ... - arXiv
Mar 3, 2025 · It is well known that the graph isomorphism problem is polynomial-time reducible to the graph automorphism problem (in fact these two problems ...
[42]
[PDF] The Complexity of Planar Graph Isomorphism - Uni Ulm
The Graph Isomorphism problem restricted to planar graphs has been known to be solvable in polynomial time many years ago. In terms of com- plexity classes ...
[43]
https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.190/Mitarbeiter/toran/beatcs09.pdf
[44]
Canonical Labeling -- from Wolfram MathWorld
A canonical labeling, also called a canonical form, of a graph G is a graph G^' which is isomorphic to G and which represents the whole isomorphism class of G.Missing: definition | Show results with:definition
[45]
Graphs, isomorphism, and canonical labeling — The bliss tool ...
A canonical labeling of G (under ρ) is an isomorphism of G onto its canonical form ρ(G). Given a colored graph G as input, the software tool bliss computes the ...
[46]
[PDF] Canonical labeling of graphs
ABSTRACT. We announce an algebraic approach to the problem of assigning canon~oal forms to graphs. We compute canonical forms and the associated.
[47]
Introduction - Nauty Traces
Sep 7, 2025 · The process of finding the canonical member of the isomorphism class containing a given object is called canonical labeling. Two labeled ...
[48]
The nauty Traces page
The original design of nauty is in B. D. McKay, Practical Graph Isomorphism, Congressus Numerantium, 30 (1981) 45-87. A scan is available. The original design ...
[49]
https://users.cecs.anu.edu.au/~bdm/nauty/
[50]
A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs
In contrast, this paper focuses on exact graph pattern mining, where we adopt the VF2 algorithm (Cordella et al. 2004 ) for subgraph isomorphism detection ...
[51]
[PDF] Weisfeiler-Lehman Graph Kernels
Our graph kernels use concepts from the Weisfeiler-Lehman test of isomorphism (Weisfeiler and. Lehman, 1968), more specifically its 1-dimensional variant, also ...
[52]
Nauty Traces – Home
Nauty Traces Home: Graph canonical labeling and automorphism group computation for graph isomorphism. ... dretodot is a tool for drawing graphs in dreadnaut ...Introduction · Traces · Search Tree · Low Degree Vertices
[53]
[1710.04574] Graph isomorphisms in quasi-polynomial time - arXiv
Oct 12, 2017 · This paper discusses graph isomorphisms, asking if two graphs are isomorphic, and how to find isomorphisms in quasi-polynomial time, which is \ ...Missing: 2024 2025
[54]
Graph Isomorphism update, January 9, 2017 - Full-Time Faculty
Jan 9, 2017 · The Graph Isomorphism test runs in quasipolynomial time (now really). The replacement consists of a few lines of pseudocode, analyzed via a simple new lemma.Missing: partial | Show results with:partial