The group isomorphism problem consists in deciding whether two groups $G$ and $H$
given by their multiplication tables are isomorphic.
An algorithm for group isomorphism attributed to Tarjan runs in time $n^{\log n + O(1)}$, c.f. [Mil78].
Miller and Monk showed in [Mil79] that group isomorphism can be many-one reduced to
isomorphism testing for directed graphs.
For groups with $n$ elements, the graphs have valence at least $n$.
We introduce a different reduction for isomorphism testing,
where the valence of the graphs, say $X(G)$ and $X(H)$,
and the complexity of the isomorphism test
is closely related to the structure of the groups.
Let $\mathcal{G}$ be the class of groups
having a composition series
where composition factors of size at least $\log n / \log\log n$
come before the others.
The composition series isomorphism problem
is given two composition series $S$ for $G$ and $S'$ for $H$,
such that any subgroup of $G$ according to $S$ is mapped blockwise onto that of $H$ according to $S'$.
In the reduction onto graph isomorphism, we get graphs $X(G,S)$ and $X(H,S')$.
Then for $p$-groups we find such an isomorphism in time $n^{cp}$ and for
the more general class of $\mathcal{G}$-groups
in time $n^{c\log n / \log\log n}$ for a constant $c$.
We analyze the time complexity for three isomorphism testing algorithms
with respect to two parameters $\beta, \gamma$ which depend on the group structure.
With a combination of the algorithms we also can show that $\mathcal{G}$-group
isomorphism is in time $n^{c (\gamma + \log\beta + \log n / \log\log n)}$,
and $p$-group isomorphism is in time $n^{c(p + \gamma + \log \beta)}$
with $\beta, \gamma \leq \log_p n$.
Most recently,
D.~Rosenbaum improves in [Ros12] these bounds
to $n^{(1/2)\log n + O(1)}$ for $p$-groups and nilpotent groups,
and to $n^{(1/2)\log n + O(\log n / \log\log n)}$ for solvable groups.
The construction process to generalize the bounds for composition series isomorphism to general groups in the previous revision was found to be not correct by D. Rosenbaum.
The group isomorphism problem consists in deciding whether two groups $G$ and $H$
given by their multiplication tables are isomorphic.
An algorithm for group isomorphism attributed to Tarjan runs in time $n^{\log n + O(1)}$, c.f. [Mil78].
Miller and Monk showed in~[Mil79] that group isomorphism can be many-one reduced to
isomorphism testing for directed graphs.
For groups with $n$ elements, the graphs have valence at least $n$.
We introduce a different reduction for isomorphism testing,
where the valence of the graphs, say $X(G)$ and $X(H)$,
and the complexity of the isomorphism test
is closely related to the structure of the groups.
The \emph{composition series isomorphism problem}
is given two composition series $S$ for $G$ and $S'$ for $H$,
such that any subgroup of $G$ according to $S$ is mapped blockwise onto that of $H$ according to $S'$.
In the reduction onto graph isomorphism, we get graphs $X(G,S)$ and $X(H,S')$.
Then for $p$-groups we find such an isomorphism in time $n^{cp}$ and for
general groups in time $n^{c\log n / \log\log n}$, for a constant $c$.
As pointed out by D. Rosenbaum [Ros12],
there was an error in an earlier version of this work.
This affected the bound of composition series isomorphism for general groups,
and remained correct for $p$-groups.
Therefore, we introduce a new processing step for general groups.
We analyze the time complexity for three isomorphism testing algorithms
with respect to two parameters $\beta, \gamma$ which depend on the group structure.
With a combination of the algorithms we also can show that group isomorphism is in
time $n^{c (\gamma + \log\beta + \log n / \log\log n)}$,
and $p$-group isomorphism is in time $n^{c(p + \gamma + \log \beta)}$
with $\beta, \gamma \leq \log_p n$.
Most recently, D.~Rosenbaum improves in~[Ros12] these bounds
to $n^{(1/2)\log n + O(1)}$ for $p$-groups and nilpotent groups,
and to $n^{(1/2)\log n + O(\log n / \log\log n)}$ for solvable groups.
Corrections in abstract and the introduction.
The group isomorphism problem consists in deciding whether two groups $G$ and $H$
given by their multiplication tables are isomorphic.
An algorithm for group isomorphism attributed to Tarjan runs in time $n^{\log n + O(1)}$, c.f.~[Mil78].
Miller and Monk showed in~[Mil79] that group isomorphism can be many-one reduced to
isomorphism testing for directed graphs.
For groups with $n$ elements, the graphs have valence at least $n$.
We introduce a different reduction for isomorphism testing,
where the valence of the graphs, say $X(G)$ and $X(H)$,
and the complexity of the isomorphism test
is closely related to the structure of the groups.
The \emph{composition series isomorphism problem}
is given two composition series $S$ for $G$ and $S'$ for $H$,
such that any subgroup of $G$ according to $S$ is mapped blockwise onto that of $H$ according to $S'$.
In the reduction onto graph isomorphism, we get graphs $X(G,S)$ and $X(H,S')$.
Then for $p$-groups we find such an isomorphism in time $n^{cp}$ and for
general groups in time $n^{c\log n / \log\log n}$, for a constant $c$.
We analyze the time complexity for three isomorphism testing algorithms
with respect to two parameters which depend on the group structure.
With a combination of the algorithms we also can show that $p$-group isomorphism is in
time $n^{c\log n / \log \log n}$.
D. Rosenbaum showed in~[Ros12] that this bound can be generalized to nilpotent groups.
As pointed out by D. Rosenbaum [Ros12],
there was an error in a previous version of this work.
This affected the bound of composition series isomorphism for general groups,
the bounds remained correct for composition series isomorphism
and group isomorphism for $p$-groups.
A new processing step is introduced to apply the techniques used in a reduction to graph isomorphism for general groups.
The group isomorphism problem consists in deciding whether two groups $G$ and $H$
given by their multiplication tables are isomorphic.
An algorithm for group isomorphism attributed to Tarjan runs in time $n^{\log n + O(1)}$, c.f. [Mil78].
Miller and Monk showed in [Mil79] that group isomorphism can be many-one reduced to
isomorphism testing for directed graphs.
For groups with $n$ elements, the graphs have valence at least $n$.
We introduce a different reduction embedded in isomorphism tests,
where the valence of the graphs, say $X(G)$ and $X(H)$,
and the complexity of the isomorphism test
is closely related to the structure of the groups.
When given additionally to the input a composition series $S$ for $G$ and $S'$ for $H$,
then in the reduction we get graphs $X(G,S), X(H,S')$ where
an isomorphism $\phi$ from $X(G,S)$ onto $X(H,S')$ gives an isomorphism $\phi'$ from $G$ onto $H$
such that $\phi'$ maps the subgroups in $S$ blockwise onto those in $S'$.
Then for $p$-groups, the reduction runs in time $n^{cp}$
and for general groups in time $n^{c\log n / \log\log n}$, for a constant $c$.
Conversely, finding such composition series for the groups,
i.e., such that there are isomorphisms that respect them,
is as hard as the group isomorphism problem.
We analyze the time complexity for three isomorphism testing algorithms
with respect to two parameters which depend on the group structure.
There was an error in the previous version which affected the main result.
We consider now
- group isomorphism when given additionally composition series to the input groups,
- the time complexity of group isomorphism with respect to
two parameters which depend on the group structure.
The group isomorphism problem consists in deciding whether two groups $G$ and $H$
given by their multiplication tables are isomorphic.
An algorithm for group isomorphism attributed to Tarjan runs in time $n^{\log n + O(1)}$, c.f. [Mil78].
Miller and Monk showed in [Mil79] that group isomorphism can be many-one reduced to
isomorphism testing for directed graphs.
For groups with $n$ elements, the graphs have valence at least $n$.
We many-one reduce group isomorphism onto graph isomorphism,
such that the valence of the graphs is at most $d+1$ if
$d$ is the size of the largest factor group in a composition series of the groups.
Combining this with the fact that isomorphism testing for graphs of valence $d$ can be solved in time $n^{O(d)}$,
$p$-group isomorphism is in time $n^{cp}$ for a constant $c$.
We extend this algorithm to work for general groups,
improving the exponential runtime behavior if factor groups of large size exist.
Then we also consider the following simple group isomorphism algorithm,
namely we compute a composition series and then guess coset representatives as generators.
This algorithm has the same worst-case behavior as Tarjans algorithm.
But if we combine both algorithms
then we can show that group isomorphism is in time $n^{c\log n / \log\log n}$ for a constant $c$.
As noted by L. Babai the proof of Lemma 4.9 is not correct because the composition series computed by Algorithm 1 do not satisfy the isomorphism properties stated in this lemma.
This affects the main result of the paper.
D. Rosenbaum mentioned in arXiv:1205.0642
an error that affects the main result of the paper, such that Corollary 1.3 is true not for all groups.
It is correct e.g. for $p$-groups and an interesting
more general class of groups with given composition series $S$, where factor groups of size less than $\alpha$ come before the others in $S$.
There is an updated and improved version
of the results for p-groups in arXiv:1205.0642 and TR11-052 in ECCC, see arXiv:1312.1755.
