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 (104)

• 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
• Hodge Laplacians on graphs
• 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
• Comparing Graphs via Persistence Distortion
• 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
• Enumerating Unique Computational Graphs via an Iterative Graph Invariant
• Hybrid ASP-based Approach to Pattern Mining
• Strongly polynomial sequences as interpretations
• On the Combinatorial Power of the Weisfeiler-Lehman Algorithm
• 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
• Lorentzian Spectral Geometry with Causal Sets
• Unseeded low-rank graph matching by transform-based unsupervised point registration
• On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties
• The Phantom Alignment Strength Conjecture: Practical use of graph matching alignment strength to indicate a meaningful graph match
• Graph Isomorphism for unit square graphs
• Discriminating Non-Isomorphic Graphs with an Experimental Quantum Annealer
• SPECTRE: Seedless Network Alignment via Spectral Centralities
• Polynomial-time isomorphism testing of groups of most finite orders
• Interpretable Stability Bounds for Spectral Graph Filters
• Reconstruction for Powerful Graph Representations
• Minimal definable graphs of definable chromatic number at least three
• Exact Matching of Random Graphs with Constant Correlation
• Semidefinite Programming Approach for the Quadratic Assignment Problem with a Sparse Graph
• Complexity of the Fourier transform on the Johnson graph
• Local, global and scale-dependent node roles
• VerSaChI: Finding Statistically Significant Subgraph Matches using Chebyshev's Inequality
• The Atlas for the Aspiring Network Scientist
• Consistent polynomial-time unseeded graph matching for Lipschitz graphons
• On the Baer-Lovász-Tutte construction of groups from graphs: isomorphism types and homomorphism notions
• Social Network De-anonymization: More Adversarial Knowledge, More Users Re-Identified?
• The quantum algorithm for graph isomorphism problem
• On Graph Isomorphism Problem
• Upper Bounds on the Quantifier Depth for Graph Differentiation in First-Order Logic
• Quantum State Isomorphism
• Algorithmic Aspects of Regular Graph Covers
• Random Graph Matching with Improved Noise Robustness
• A Topological Algorithm for Determining How Road Networks Evolve Over Time
• On short expressions for cosets of permutation subgroups
• From independent sets and vertex colorings to isotropic spaces and isotropic decompositions
• P?=NP as minimization of degree 4 polynomial, integration or Grassmann number problem, and new graph isomorphism problem approaches
• On the Automorphism Group of a Graph
• Quantum Fourier Sampling is Guaranteed to Fail to Compute Automorphism Groups of Easy Graphs
• The Graph Isomorphism Problem: Local Certificates for Giant Action
• On the Universality of Graph Neural Networks on Large Random Graphs
• Computing normalisers of intransitive groups
• Partition and Code: learning how to compress graphs
• Primitive normalisers in quasipolynomial time
• Minimal generating sets for matrix monoids
• A Framework to Quantify Approximate Simulation on Graph Data
• On the Weisfeiler-Leman Dimension of Fractional Packing
• On the number of fixed points of automorphisms of vertex-transitive graphs of bounded valency
• On Tail Dependence Matrices -- The Realization Problem for Parametric Families
• Towards a CFSG-free diameter bound for $\mathrm{Alt}(n)$
• Searching for square-complementary graphs: non-existence results and complexity of recognition
• Induced Minor Free Graphs: Isomorphism and Clique-width
• Reduction of the graph isomorphism problem to equality checking of $n$-variables polynomials and the algorithms that use the reduction
• Perfect weak modular product graphs
• Approximations of Isomorphism and Logics with Linear-Algebraic Operators
• A new algebraic approach to the graph isomorphism and clique problems
• The super-connectivity of Johnson graphs
• A graph-theoretic framework for algorithmic design of experiments
• Revisiting the Graph Isomorphism Problem with Semidefinite Programming
• On the automorphism groups of distance-regular graphs and rank-4 primitive coherent configurations
• Doubly-Efficient Pseudo-Deterministic Proofs
• A Blind Permutation Similarity Algorithm
• Graph Embedding via Diffusion-Wavelets-Based Node Feature Distribution Characterization
• Casting graph isomorphism as a point set registration problem using a simplex embedding and sampling
• Game of Life on Graphs
• Fractional hypergraph isomorphism and fractional invariants
• Completeness in Polylogarithmic Time and Space
• Cryptography with right-angled Artin groups
• Using Laplacian Spectrum as Graph Feature Representation
• On the Lattice Distortion Problem
• Canonical Number and NutCracker: Heuristic Algorithms for the Graph Isomorphism Problem using Free Energy
• Visual Detection of Structural Changes in Time-Varying Graphs Using Persistent Homology
• On the Parallel Parameterized Complexity of the Graph Isomorphism Problem
• Baby-Step Giant-Step Algorithms for the Symmetric Group
• Logic Programming with Graph Automorphism: Integrating naut with Prolog (Tool Description)
• A Simple Algorithm for a Computationally Hard Problem
• Network Alignment by Discrete Ollivier-Ricci Flow