Graph isomorphism problem and 2-closed permutation groups

DOI10.1007/BF01196622MaRDI QIDQ1311608zbMATH OpenFDO

Authors Ilya Ponomarenko

Publication date 4 January 1995

Published in Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01196622

zbMATH Keywords

2-closed permutation groups2-closurealgorithmic problemscoherent configurationsgraph isomorphism problemnilpotent permutation grouppolynomial time algorithmstrong generating set

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) General theory for finite permutation groups (20B05) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25) Sylow subgroups, Sylow properties, (pi)-groups, (pi)-structure (20D20) Generators, relations, and presentations of groups (20F05) Analysis of algorithms and problem complexity (68Q25)

Review text

The purpose of the paper is twofold. First, the author gives a polynomial time algorithm for finding a strong generating set of the 2-closure of a nilpotent permutation group. (He notices that this 2-closure is solvable. One can see that it is even nilpotent.) Second, the author proves that for 2-closed permutation groups several notoriously hard algorithmic problems are actually polynomially equivalent to the graph isomorphism problem, in particular finding intersections, setwise stabilizers, normalizers and testing conjugacy. Three equivalent problems for coherent configurations are also mentioned. \{There is a misprint in the crucial definition of \(\overline{g}_ i\) on p. 17, and even if this is corrected the proof can work only for undirected graphs\}.

Recommendations

• Two-closure of rank \(3\) groups in polynomial time
• Two-closure of odd permutation group in polynomial time
• scientific article; zbMATH DE number 96386
• The 2-closure of a \(\frac{3}{2}\)-transitive group in polynomial time
• Permutation Groups and the Graph Isomorphism Problem

Cites work

• A note on the graph isomorphism counting problem
• A polynomial bound for the orders of primitive solvable groups
• scientific article; zbMATH DE number 3841910 (Why is no real title available?)
• scientific article; zbMATH DE number 3991749 (Why is no real title available?)
• scientific article; zbMATH DE number 3223737 (Why is no real title available?)
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• On the 2-Closures of Finite Permutation Groups
• Polynomial time recognition and isomorphism testing for cyclic tournaments
• Sylow's theorem in polynomial time

Cited in

(12)

• On finite totally \(2\)-closed groups
• The 2-closure of a \(\frac{3}{2}\)-transitive group in polynomial time
• Closures of finite permutation groups
• Permutation Groups and the Graph Isomorphism Problem
• Finite nilpotent groups that coincide with their 2-closures in all of their faithful permutation representations
• GROUP, GRAPHS, ALGORITHMS: THE GRAPH ISOMORPHISM PROBLEM
• Two-closure of odd permutation group in polynomial time
• Two-closure of rank \(3\) groups in polynomial time
• On computing the closures of solvable permutation groups
• Closures of permutation groups with restricted nonabelian composition factors
• Two-closures of supersolvable permutation groups in polynomial time
• On the asymmetric complexity of the group-intersection problem

This page was built for publication: Graph isomorphism problem and \(2\)-closed permutation groups

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