Graph isomorphism in quasipolynomial time [extended abstract]
From MaRDI portal
Publication:5361871
DOI10.1145/2897518.2897542zbMath1376.68058OpenAlexW2409645877MaRDI QIDQ5361871
Publication date: 29 September 2017
Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2897518.2897542
Analysis of algorithms and problem complexity (68Q25) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items
Exponentially many graphs have a \(Q\)-cospectral mate ⋮ On fixity of arc-transitive graphs ⋮ Graph isomorphism and Gaussian boson sampling ⋮ Towards Efficient Normalizers of Primitive Groups ⋮ Detecting almost symmetries of graphs ⋮ Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs ⋮ The QAP-polytope and the graph isomorphism problem ⋮ Minimum Circuit Size, Graph Isomorphism, and Related Problems ⋮ Geometry and Combinatorics via Right-Angled Artin Groups ⋮ Computing normalisers of intransitive groups ⋮ Unnamed Item ⋮ Parallel Algorithm for Solving the Graph Isomorphism Problem ⋮ Maximum Likelihood Estimation and Graph Matching in Errorfully Observed Networks ⋮ Asymmetric coloring of locally finite graphs and profinite permutation groups: Tucker's conjecture confirmed ⋮ Exact Recovery with Symmetries for the Doubly Stochastic Relaxation ⋮ A fast Fourier transform for the Johnson graph ⋮ Nominal Unification and Matching of Higher Order Expressions with Recursive Let ⋮ Practical post-quantum signature schemes from isomorphism problems of trilinear forms ⋮ Uniform random posets ⋮ Graph isomorphism for \((H_1, H_2)\)-free graphs: an almost complete dichotomy ⋮ Lov\'asz Meets Weisfeiler and Leman ⋮ An improved isomorphism test for bounded-tree-width graphs ⋮ Zero knowledge and circuit minimization ⋮ General linear group action on tensors: a candidate for post-quantum cryptography ⋮ Baby-step giant-step algorithms for the symmetric group ⋮ Some conditionally hard problems on links and 3-manifolds ⋮ Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets ⋮ Robust worst cases for parity games algorithms ⋮ QUBO formulations for the graph isomorphism problem and related problems ⋮ A graph isomorphism condition and equivalence of reaction systems ⋮ Quantum and non-signalling graph isomorphisms ⋮ Drags: a compositional algebraic framework for graph rewriting ⋮ The resistance perturbation distance: a metric for the analysis of dynamic networks ⋮ Towards an isomorphism dichotomy for hereditary graph classes ⋮ Efficient isomorphism for \(S_d\)-graphs and \(T\)-graphs ⋮ Space efficient representations of finite groups ⋮ Normalisers of primitive permutation groups in quasipolynomial time ⋮ Induced minor free graphs: isomorphism and clique-width ⋮ Card-based zero-knowledge proof protocols for graph problems and their computational model ⋮ Generalizations of \(k\)-dimensional Weisfeiler-Leman stabilization ⋮ Unnamed Item ⋮ Reconstructing Generalized Staircase Polygons with Uniform Step Length ⋮ Hodge Laplacians on Graphs ⋮ Network alignment by discrete Ollivier-Ricci flow ⋮ Listing Maximal Subgraphs Satisfying Strongly Accessible Properties ⋮ Spectrally Robust Graph Isomorphism ⋮ Upper Bounds on the Quantifier Depth for Graph Differentiation in First Order Logic ⋮ On the generalized spectral characterizations of Eulerian graphs ⋮ Discrete-time quantum walk search on Johnson graphs ⋮ On the Baer-Lovász-Tutte construction of groups from graphs: isomorphism types and homomorphism notions ⋮ Minimal definable graphs of definable chromatic number at least three ⋮ Local WL invariance and hidden shades of regularity ⋮ Graph Similarity and Approximate Isomorphism ⋮ STUDY OF GRAPH ISOMORPHISM USING JORDAN FORMS OF ADJACENCY MATRICES ⋮ Configuring Random Graph Models with Fixed Degree Sequences ⋮ Polynomial-time algorithm for isomorphism of graphs with clique-width at most three ⋮ Constructing quantum hash functions based on quantum walks on Johnson graphs ⋮ Public-key cryptosystem based on invariants of diagonalizable groups ⋮ Uniquely pressable graphs: characterization, enumeration, and recognition ⋮ Unnamed Item ⋮ Benchmark Graphs for Practical Graph Isomorphism ⋮ Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable ⋮ Searching for square-complementary graphs: complexity of recognition and further nonexistence results ⋮ Minimum Circuit Size, Graph Isomorphism, and Related Problems ⋮ A completely positive formulation of the graph isomorphism problem and its positive semidefinite relaxation ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The robustness of LWPP and WPP, with an application to graph reconstruction ⋮ Sparse random matrices have simple spectrum ⋮ Reconstructing Generalized Staircase Polygons with Uniform Step Length ⋮ On short expressions for cosets of permutation subgroups ⋮ Two-line graphs of partial Latin rectangles ⋮ The Weisfeiler-Leman algorithm and the diameter of Schreier graphs ⋮ Hybrid ASP-based Approach to Pattern Mining ⋮ Inverse monoids of partial graph automorphisms ⋮ The Weisfeiler-Leman dimension of chordal bipartite graphs without bipartite claw ⋮ Constructing non-isomorphic signless Laplacian cospectral graphs ⋮ Solution-Graphs of Boolean Formulas and Isomorphism ⋮ Refining invariants for computing autotopism groups of partial Latin rectangles ⋮ The Complexity of Homomorphism Indistinguishability ⋮ The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs ⋮ On the number of fixed points of automorphisms of vertex-transitive graphs ⋮ A Generic Framework for Engineering Graph Canonization Algorithms ⋮ A new arithmetic criterion for graphs being determined by their generalized \(Q\)-spectrum ⋮ Knowledge representation analysis of graph mining ⋮ Approximate lumpability for Markovian agent-based models using local symmetries ⋮ Primitive normalisers in quasipolynomial time ⋮ Unnamed Item ⋮ From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces ⋮ Kernelization of Whitney Switches ⋮ Constructing cospectral bipartite graphs ⋮ Identifiability of Graphs with Small Color Classes by the Weisfeiler--Leman Algorithm ⋮ Fractional isomorphism of graphons ⋮ Classical symmetries and the quantum approximate optimization algorithm ⋮ Solution-Graphs of Boolean Formulas and Isomorphism1 ⋮ Isomorphism Test for Digraphs with Weighted Edges. ⋮ The Power of the Weisfeiler--Leman Algorithm to Decompose Graphs ⋮ LESS-FM: fine-tuning signatures from the code equivalence problem ⋮ Finding fixed point free elements and small bases in permutation groups ⋮ Isomorphism Testing for Graphs Excluding Small Minors ⋮ Algorithms for Group Isomorphism via Group Extensions and Cohomology ⋮ On the Combinatorial Power of the Weisfeiler-Lehman Algorithm ⋮ Stathis Zachos at 70! ⋮ On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness ⋮ Exact Recovery with Symmetries for Procrustes Matching ⋮ Exact matching of random graphs with constant correlation ⋮ Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable (extended abstract) ⋮ Computing Autotopism Groups of Partial Latin Rectangles ⋮ A subquadratic algorithm for the simultaneous conjugacy problem ⋮ Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications ⋮ Order Reconfiguration under Width Constraints ⋮ Hull attacks on the lattice isomorphism problem ⋮ Filtered simplicial homology, graph dissimilarity and überhomology ⋮ On the computational hardness of the code equivalence problem in cryptography ⋮ An Isomorphism-Invariant Distance Function on Propositional Formulas in CNF ⋮ Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas ⋮ Modular rewritable Petri nets: an efficient model for dynamic distributed systems ⋮ Graphs isomorphisms under edge-replacements and the family of amoebas ⋮ A Faster Isomorphism Test for Graphs of Small Degree ⋮ On the automorphism groups of rank-4 primitive coherent configurations ⋮ Data Structures for Topologically Sound Higher-Dimensional Diagram Rewriting ⋮ Two remarks on the vectorization problem ⋮ Isomorphism Testing Parameterized by Genus and Beyond ⋮ Lackadaisical discrete-time quantum walk on Johnson graph ⋮ Unnamed Item ⋮ Constructing Hard Examples for Graph Isomorphism ⋮ Improved Algorithms for Alternating Matrix Space Isometry: From Theory to Practice ⋮ On the Weisfeiler-Leman dimension of fractional packing ⋮ Recognizing hyperelliptic graphs in polynomial time ⋮ An adaptive prefix-assignment technique for symmetry reduction ⋮ Graph isomorphism restricted by lists ⋮ On the geometry of symmetry breaking inequalities ⋮ On Weisfeiler-Leman invariance: subgraph counts and related graph properties ⋮ On the geometry of symmetry breaking inequalities ⋮ The Weisfeiler-Leman algorithm and recognition of graph properties ⋮ The Weisfeiler-Leman algorithm and recognition of graph properties ⋮ Kernelization of Whitney Switches ⋮ Computational Complexity of Computing Symmetries in Finite-Domain Planning ⋮ Improved Hardness of Maximum Common Subgraph Problems on Labeled Graphs of Bounded Treewidth and Bounded Degree ⋮ Canonisation and Definability for Graphs of Bounded Rank Width
This page was built for publication: Graph isomorphism in quasipolynomial time [extended abstract]
