A Faster Isomorphism Test for Graphs of Small Degree

DOI10.1137/19M1245293arXiv1802.04659OpenAlexW3007883572MaRDI QIDQ6139827FDOQ6139827

Authors: Martin Grohe, Daniel Neuen, P. Schweitzer 

Publication date: 19 December 2023

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Abstract: In a recent breakthrough, Babai (STOC 2016) gave a quasipolynomial time graph isomorphism test. In this work, we give an improved isomorphism test for graphs of small degree: our algorithms runs in time $n^{O((logd{)}^c)}$, where $n$ is the number of vertices of the input graphs, $d$ is the maximum degree of the input graphs, and $c$ is an absolute constant. The best previous isomorphism test for graphs of maximum degree $d$ due to Babai, Kantor and Luks (FOCS 1983) runs in time $n^{O(d/logd)}$.

Full work available at URL: https://arxiv.org/abs/1802.04659

Recommendations

• Graph isomorphisms in quasi-polynomial time [after Babai and Luks, Weisfeiler-Leman,\ldots]
• Recent advances on the graph isomorphism problem
• An improved isomorphism test for bounded-tree-width graphs
• An improved isomorphism test for bounded-tree-width graphs
• Isomorphism testing for graphs excluding small topological subgraphs

zbMATH Keywords

graph isomorphismpermutation groupsbounded degree graphsgroups with restricted composition factors

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Primitive groups (20B15)

Cites Work

• Title not available (Why is that?)
• The maximal subgroups of the low-dimensional finite classical groups.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Bases of primitive linear groups.
• Bases of primitive linear groups. II.
• Title not available (Why is that?)
• Simple groups, permutation groups, and probability
• Title not available (Why is that?)
• Finite Permutation Groups and Finite Simple Groups
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• The isomorphism problem for classes of graphs closed under contraction
• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
• Title not available (Why is that?)
• Graph isomorphism for graph classes characterized by two forbidden induced subgraphs
• Structure theorem and isomorphism test for graphs with excluded topological subgraphs
• On minimal degrees and base sizes of primitive permutation groups
• On the orders of primitive groups with restricted nonabelian composition factors
• On the orders of primitive groups
• Graph isomorphism, general remarks
• Graph isomorphism in quasipolynomial time (extended abstract)
• Minimal degree for a permutation representation of a classical group
• Title not available (Why is that?)
• Bases for primitive permutation groups and a conjecture of Babai
• An improved isomorphism test for bounded-tree-width graphs

Cited In (4)

• Isomorphism testing for graphs excluding small topological subgraphs
• A completely positive formulation of the graph isomorphism problem and its positive semidefinite relaxation
• Title not available (Why is that?)
• Efficient Method to Perform Isomorphism Testing of Labeled Graphs

This page was built for publication: A Faster Isomorphism Test for Graphs of Small Degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6139827)