A fast algorithm for Stallings foldings over virtually free groups

Abstract

We give a simple algorithm to solve the subgroup membership problem for virtually free groups. For a fixed virtually free group with a fixed generating set $X$, the subgroup membership problem is uniformly solvable in time $O(n{\log }^{\ast }(n))$ where $n$ is the sum of the word lengths of the inputs with respect to $X$. For practical purposes, this can be considered to be linear time. The algorithm itself is simple and concrete examples are given to show how it can be used for computations in $\mathrm{SL}(2,\mathbb{Z})$ and $\mathrm{GL}(2,\mathbb{Z})$. We also give an algorithm to decide whether a finitely generated subgroup is isomorphic to a free group.

29 pages, 9 Figures. Revised after referee comments