A fast algorithm for Stallings foldings over virtually free groups

We give a simple algorithm to solve the subgroup membership problem for virtually free groups given as a graph of finite groups. For a fixed virtually free group with a fixed generating set X, the subgroup membership problem is uniformly solvable in time [Formula: see text] 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 is simple enough to work out small examples by hand and concrete examples are given to show how it can be used for computations in [Formula: see text] and [Formula: see text]. We also give fast algorithm to decide whether a finitely generated subgroup of a virtually free group is free.