Practical graph isomorphism, II

2013/01/08 by Brendan D. McKay, McKay, Brendan D., Adolfo Piperno +1 · 75 citations
Computer Science · Mathematics · #05C85 #20B40 #68R10 #Advanced Graph Theory Research #BLISS #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computer science #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph #Graph Theory and Algorithms #Graph isomorphism #Isomorphism (crystallography) #Line graph #Programming language #Theoretical computer science #cs.DM #math.CO #msc:05C85 #msc:20B40 #msc:68R10

paper · pdf · doi:10.48550/arxiv.1301.1493

published in arXiv (Cornell University) (Cornell University) · This is partially a replacement for http://arxiv.org/abs/0804.4881

arxiv created 2013/01/08 · openalex publication_date 2013/01/08 · arxiv updated 2013/01/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We report the current state of the graph isomorphism problem from the practical point of view. After describing the general principles of the refinement-individualization paradigm and proving its validity, we explain how it is implemented in several of the key programs. In particular, we bring the description of the best known program nauty up to date and describe an innovative approach called Traces that outperforms the competitors for many difficult graph classes. Detailed comparisons against saucy, Bliss and conauto are presented.

Citations

• Search Space Contraction in Canonical Labeling of Graphs
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Isomorphism testing for graphs of bounded genus
• A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus
• The graph isomorphism disease
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees

Cited by

• Balance Constants, Majority Cycles, and the Gold Partition Conjecture through Fourteen Elements
• The Uhlenbeck-Ford model in two dimensions: Reference system for fluid-phase free-energy calculations
• Symmetry of Spin Systems as Automorphisms of Undirected Weighted Graphs: Realizability Criterion and Complete Taxonomy up to 14 Spins
• The Excluded Vertex-Minors and Pivot-Minors for Rank-Width at Most Two
• On the Genus Polynomial of Cubic Graphs
• An infinite family of minimally nonperfectly divisible graphs with a bisimplicial vertex
• Two-level D- and A-optimal designs of Ehlich type with run sizes three more than a multiple of four
• Graph Isomorphism: Mixed-Integer Convex Optimization from First-Order Methods
• On the transmission irregular trees with the maximum Wiener index
• Classification of borderenergetic chemical graphs and borderenergetic graphs of order 12
• Mixed updating in structured populations
• Resolvable Triple Arrays
• On the Number of Posets
• A census of Cayley graphs
• Computing Treedepth Obstructions
• Efficient Identification of Permutation Symmetries in Many-Body Hamiltonians via Graph Theory
• A Framework for Handling and Exploiting Symmetry in Benders' Decomposition
• On the order-diameter ratio of girth-diameter cages
• The SCIP Optimization Suite 10.0
• Magnetostriction in the J-K-Γ model: Application of the numerical linked cluster expansion
• A Note on Large Degenerate Induced Subgraphs in Sparse Graphs
• SeQuant Framework for Symbolic and Numerical Tensor Algebra. I. Core Capabilities
• A Systematic Study of Single-Anchor Logical Gadgets
• Steiner systems S(2,6,226) and S(2,6,441) exist
• The Cloven Traveling Salesman: Cycle Covers and the Integrality Gap of Small ATSP Instances
• Equivalence of complex Hadamard matrices
• Enumeration of Tree-like Multigraphs with a Given Number of Vertices, Self-loops and Multiple Edges
• A Classification of Long-Refinement Graphs for Colour Refinement
• Three-dimensional symmetric designs of propriety 3
• Universally Invariant Learning in Equivariant GNNs
• Engineering Dominating Patterns: A Fine-grained Case Study
• A Faster Randomized Algorithm for Vertex Cover: An Automated Approach
• Graph2Region: Efficient Graph Similarity Learning with Structure and Scale Restoration
• On the maximal spread of symmetric Bohemian matrices
• Progress in the study of the (non)existence of genuinely unextendible product bases
• IMProofBench: Benchmarking AI on Research-Level Mathematical Proof Generation
• Marvelous slices of orthogonal matrices
• Steiner 3-designs as extensions
• Enumeration of Laplacian integral and -1,0,1-diagonalizable graphs
• Computations in equivariant Gromov-Witten theory of GKM spaces
• Computational Exploration of Finite Semigroupoids
• The lattice packing problem in dimension 9 by Voronoi's algorithm
• Computer-assisted graph theory: a survey
• IP Models for Minimum Zero Forcing Sets, Forts, and Related Graph Parameters
• Improved lower bounds on the maximum size of graphs with girth 5
• A Hidden Permutation Symmetry of Squared Amplitudes in ABJM Theory
• Anomalous dimensions and critical exponents for the Gross-Neveu-Yukawa model at five loops
• Tropical elliptic curves in 3-space
• Open, Reproducible Calculation of Assembly Indices
• The Multiset Dimension of Graphs: Extremal Values and King Grids
• The Cycle Counts of Graphs
• 5-regular graphs and the 3-dimensional rigidity matroid
• Infinitely many counterexamples to a conjecture of Lovász
• Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualization
• On a conjecture of Faudree and Schelp
• Orbit classification and analysis of qutrit graph states under local complementation and local scaling
• Context-dependent spatial multicellular network motifs for single-cell spatial biology
• Perfect 1-factorisations of K_11,11
• 4K₁-free graph with the cop number 3
• Constructing All Birthday 3 Games as Digraphs
• A Counterexample to a Conjecture of Lovász
• Enumerating Two-Orbit Graphs
• Ramsey with purple edges
• A 60-Vertex Lower Bound for Cubic Bipartite Counterexamples to the Erdős-Gyárfás Conjecture
• Elucidating the Size of Chemical Space with Assembly Theory
• Hypergraph Characterization of Fusion Rings
• Learning Efficiency Meets Symmetry Breaking
• Maps of Tournaments: Distances, Experiments, and Data
• Canonicalization of Batched Einstein Summations for Tuning Retrieval
• Formal Verification of Agentic Systems over Operational Data
• No three algebraic conjugates of degree sixteen sum to zero
• A Two-Player Zero Forcing Game
• Some new Steiner designs S(2,6,91)
• There are finitely many 5-vertex-critical (P₆,bull)-free graphs
• Improved approximation ratios for the Quantum Max-Cut problem on general, triangle-free and bipartite graphs
• Toric ideals of graphs minimally generated by a Gröbner basis

Related

• Recent Advances on the Graph Isomorphism Problem
• The direct algorithm for solving of the graph isomorphism problem
• Benchmark Graphs for Practical Graph Isomorphism
• Graph isomorphism and automorphism problems are polynomial
• Polynomial Time Algorithm for Graph Isomorphism Testing