A Faster Isomorphism Test for Graphs of Small Degree

DOI10.1137/19M1245293MaRDI QIDQ6139827zbMATH OpenOpenAlexFDO

Authors Martin Grohe, Daniel Neuen, P. Schweitzer

Publication date 19 December 2023

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

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

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)

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)}$.

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

Cites work

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

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
• scientific article; zbMATH DE number 3968624 (Why is no real title available?)
• 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)