Graph Isomorphism in Quasipolynomial Time

Abstract

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 solved in quasipolynomial ($\exp ((\log n{)}^{O(1)})$) time. The best previous bound for GI was $\exp (O(\sqrt{n\log n}))$, where $n$ is the number of vertices (Luks, 1983); for the other two problems, the bound was similar, $\exp (\tilde{O}(\sqrt{n}))$, where $n$ is the size of the permutation domain (Babai, 1983). The algorithm builds on Luks's SI framework and attacks the barrier configurations for Luks's algorithm by group theoretic "local certificates" and combinatorial canonical partitioning techniques. We show that in a well-defined sense, Johnson graphs are the only obstructions to effective canonical partitioning. Luks's barrier situation is characterized by a homomorphism ϕ that maps a given permutation group $G$ onto $S_k$ or $A_k$, the symmetric or alternating group of degree $k$, where $k$ is not too small. We say that an element $x$ in the permutation domain on which $G$ acts is affected by ϕ if the ϕ-image of the stabilizer of $x$ does not contain $A_k$. The affected/unaffected dichotomy underlies the core "local certificates" routine and is the central divide-and-conquer tool of the algorithm.

89 pages

References in corpus (1)

• Practical graph isomorphism, II

Cited by in corpus (101)

• Adiabatic Quantum Computing
• Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges
• How Powerful are Graph Neural Networks?
• Deep Learning on Graphs: A Survey
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• Graph Kernels: State-of-the-Art and Future Challenges
• Graph isomorphism and Gaussian boson sampling
• Exploiting Symmetry Reduces the Cost of Training QAOA
• A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants
• On the equivalence between graph isomorphism testing and function approximation with GNNs
• Quantum Computing: Lecture Notes
• Quantum Walk Search on Johnson Graphs
• Graph Comparison via the Non-backtracking Spectrum
• Provably Powerful Graph Networks
• Nominal Unification of Higher Order Expressions with Recursive Let
• Understanding Isomorphism Bias in Graph Data Sets
• The threshold for subgroup profiles to agree is $\Omega (\log n)$
• A Faster Isomorphism Test for Graphs of Small Degree
• Can Graph Neural Networks Help Logic Reasoning?
• Complexity problems in enumerative combinatorics
• Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing
• Hypergraph Isomorphism for Groups with Restricted Composition Factors
• Effective gaps are not effective: quasipolynomial classical simulation of obstructed stoquastic Hamiltonians
• On the Combinatorial Power of the Weisfeiler-Lehman Algorithm
• Hybrid ASP-based Approach to Pattern Mining
• Enumerating Unique Computational Graphs via an Iterative Graph Invariant
• On quantum invariants and the graph isomorphism problem
• Linear Programming Heuristics for the Graph Isomorphism Problem
• Topology Aware Deep Learning for Wireless Network Optimization
• Contextual Symmetries in Probabilistic Graphical Models
• Unseeded low-rank graph matching by transform-based unsupervised point registration
• On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties
• Lorentzian Spectral Geometry with Causal Sets
• The Phantom Alignment Strength Conjecture: Practical use of graph matching alignment strength to indicate a meaningful graph match
• Polynomial-time isomorphism testing of groups of most finite orders
• Minimal definable graphs of definable chromatic number at least three
• Interpretable Stability Bounds for Spectral Graph Filters
• Graph Isomorphism for unit square graphs
• SPECTRE: Seedless Network Alignment via Spectral Centralities
• Discriminating Non-Isomorphic Graphs with an Experimental Quantum Annealer
• Exact Matching of Random Graphs with Constant Correlation
• Reconstruction for Powerful Graph Representations
• Local, global and scale-dependent node roles
• Social Network De-anonymization: More Adversarial Knowledge, More Users Re-Identified?
• VerSaChI: Finding Statistically Significant Subgraph Matches using Chebyshev's Inequality
• Semidefinite Programming Approach for the Quadratic Assignment Problem with a Sparse Graph
• The Atlas for the Aspiring Network Scientist
• On the Baer-Lovász-Tutte construction of groups from graphs: isomorphism types and homomorphism notions
• The quantum algorithm for graph isomorphism problem
• Consistent polynomial-time unseeded graph matching for Lipschitz graphons
• Complexity of the Fourier transform on the Johnson graph
• Algorithmic Aspects of Regular Graph Covers
• On Graph Isomorphism Problem
• Quantum State Isomorphism
• Random Graph Matching with Improved Noise Robustness
• From independent sets and vertex colorings to isotropic spaces and isotropic decompositions
• On short expressions for cosets of permutation subgroups
• A Topological Algorithm for Determining How Road Networks Evolve Over Time
• Upper Bounds on the Quantifier Depth for Graph Differentiation in First-Order Logic
• Minimal generating sets for matrix monoids
• On the Weisfeiler-Leman Dimension of Fractional Packing
• On the number of fixed points of automorphisms of vertex-transitive graphs of bounded valency
• Primitive normalisers in quasipolynomial time
• Partition and Code: learning how to compress graphs
• Computing normalisers of intransitive groups
• On Tail Dependence Matrices -- The Realization Problem for Parametric Families
• On the Universality of Graph Neural Networks on Large Random Graphs
• Towards a CFSG-free diameter bound for $\mathrm{Alt}(n)$
• The Graph Isomorphism Problem: Local Certificates for Giant Action
• Searching for square-complementary graphs: non-existence results and complexity of recognition
• Quantum Fourier Sampling is Guaranteed to Fail to Compute Automorphism Groups of Easy Graphs
• On the Automorphism Group of a Graph
• Reduction of the graph isomorphism problem to equality checking of $n$-variables polynomials and the algorithms that use the reduction
• P?=NP as minimization of degree 4 polynomial, integration or Grassmann number problem, and new graph isomorphism problem approaches
• Induced Minor Free Graphs: Isomorphism and Clique-width
• A Framework to Quantify Approximate Simulation on Graph Data
• Canonical Number and NutCracker: Heuristic Algorithms for the Graph Isomorphism Problem using Free Energy
• A Simple Algorithm for a Computationally Hard Problem
• Baby-Step Giant-Step Algorithms for the Symmetric Group
• Revisiting the Graph Isomorphism Problem with Semidefinite Programming
• Visual Detection of Structural Changes in Time-Varying Graphs Using Persistent Homology
• Approximations of Isomorphism and Logics with Linear-Algebraic Operators
• A new algebraic approach to the graph isomorphism and clique problems
• A graph-theoretic framework for algorithmic design of experiments
• Casting graph isomorphism as a point set registration problem using a simplex embedding and sampling
• On the automorphism groups of distance-regular graphs and rank-4 primitive coherent configurations
• On the Parallel Parameterized Complexity of the Graph Isomorphism Problem
• On the Lattice Distortion Problem
• Doubly-Efficient Pseudo-Deterministic Proofs
• Cryptography with right-angled Artin groups
• A Blind Permutation Similarity Algorithm
• Logic Programming with Graph Automorphism: Integrating naut with Prolog (Tool Description)
• Game of Life on Graphs
• Fractional hypergraph isomorphism and fractional invariants
• Completeness in Polylogarithmic Time and Space
• Graph Embedding via Diffusion-Wavelets-Based Node Feature Distribution Characterization
• The super-connectivity of Johnson graphs
• Perfect weak modular product graphs
• Network Alignment by Discrete Ollivier-Ricci Flow
• Using Laplacian Spectrum as Graph Feature Representation