The isomorphism problem for finite
extensions of free groups is in PSPACE

arXiv:1802.07085v1 [math.GR] 20 Feb 2018

Géraud Sénizergues1 and Armin Weiß2
1

2

LABRI, Bordeaux, France, geraud.senizergues@u-bordeaux.fr
Universität Stuttgart, Germany, armin.weiss@fmi.uni-stuttgart.de

February 21, 2018
We present an algorithm for the following problem: given a context-free grammar for the word problem of a virtually free group G, compute a finite graph of
groups G with finite vertex groups and fundamental group G. Our algorithm is nondeterministic and runs in doubly exponential time. It follows that the isomorphism
problem of context-free groups can be solved in doubly exponential space. Moreover, if, instead of a grammar, a finite extension of a free group is given as input,
the construction of the graph of groups is in NP and, consequently, the isomorphism
problem in PSPACE.

Keywords virtually free groups, context-free groups, isomorphism problem, structure tree, graph of groups

Contents
1 Introduction

2

2 Preliminaries
3
2.1 Bass-Serre theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Context-free groups and graphs . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Optimal cuts and structure trees . . . . . . . . . . . . . . . . . . . . . . . 10
3 Bounds on the structure tree

12

4 Stronger bounds for virtually free presentations

16

5 Main results: computing graphs of groups

19

6 Slide moves and the isomorphism problem

22

7 Conclusion and open questions

23

1

1 Introduction
The study of algorithmic problems in group theory was initiated by Dehn [7] when
he introduced the word and the isomorphism problem. The word problem asks whether
some word over a (finite) set of generators represents the identity of the group. It also can
be viewed as a formal language, namely ϕ−1 (1) ⊆ Σ∗ for some surjective homomorphism
ϕ : Σ∗ → G. The isomorphism problem receives two finite presentations as input, the
question is whether the groups they define are isomorphic. Although both these problems
are undecidable in general [19, 4], there are many classes of groups where at least the
word problem can be decided efficiently.
One of these classes are the finitely generated virtually free groups (groups with a free
subgroup of finite index). It is easy to see that the word problem of a finitely generated
virtually free group can be solved in linear time. Indeed, it forms a deterministic contextfree language. A seminal paper by Muller and Schupp [17] shows the converse: every
group with a context-free word problem is virtually free. Since then, also a wide range
of other characterizations of virtually free groups have emerged – for a survey we refer
to [1, 10].
The isomorphism problem of virtually free groups is also decidable as Krstić showed
in [15] (indeed, later Dahmani and Guirardel showed that the isomorphism problem for
all hyperbolic groups is decidable [6]). Here the input consists of two arbitrary finite
presentations with the promise that both define virtually free groups. Unfortunately, the
approach in [15] does not give any bound on the complexity. For the special case where
the input is given as finite extension of free groups or as context-free grammars for the
word problems, Sénizergues [22, 23] showed that the isomorphism problem is primitive
recursive.
Contribution.

We improve the complexity for the isomorphism problem by showing:

(A) Given a context-free grammar for the word problem of a context-free group G, a
O(n2 )

graph of groups for G with finite vertex groups can be computed in NTIME(22
(Theorem 34).

)

(B) Given a virtually free presentation for G, a graph of groups for G with finite vertex
groups can be computed in NP (Theorem 35).
(C) The isomorphism problem for context-free groups given as grammars is in
O(n2 )

DSPACE(22

) (Theorem 38).

(D) The isomorphism problem for virtually free groups given as virtually free presentations is in PSPACE (Theorem 39).
Here, a virtually free presentation for G consists of a free group F plus a set of representatives S for F \G together with relations describing pairwise multiplications of elements
from F and S. Typical examples of virtually free presentations are finite extensions of
free groups. For non-deterministic function problems we use the convention, that every

2

accepting computation must yield a correct result; but the results of different accepting
computations might differ1 .
The results (C) and (D) can seen be to follow from (A) and (B) by using parts of
Krstić’s algorithm for the isomorphism problem. Here, we present another approach
based on so-called slide moves on the graph of groups. Indeed, we conclude from
Forester’s work on deformation spaces [11] that two graphs of groups with finite vertex groups and isomorphic fundamental groups can be transformed into each other by a
sequence of slide moves (Proposition 36).
Our approach for proving (A) and (B) is as follows: in both cases the algorithm simply
guesses a graph of groups together with a map and afterwards it verifies deterministically
whether the map is indeed an isomorphism. The latter can be done using standard results
from formal language theory. The difficult part is to show the existence of a “small”
graph of groups and isomorphism (within the bounds of (A) and (B)).
For this, we introduce the structure tree theory by Dicks and Dunwoody [8] following
a slightly different approach by Diekert and Weiß [9] based on the optimal cuts of the
Cayley graph (Section 2.3). The optimal cuts can be seen as the edge set of some tree
on which the group G acts. By Bass-Serre theory, this yields the graph of groups we are
aiming for. Vertices in the graph of groups are defined in terms of equivalence classes of
optimal cuts. The key in the proof is to bound the size of the equivalence classes. Using
Muller and Schupp’s [17] notion of k-triangulability, Snizergues [23] proved bounds on
the size of finite subgroups and on the number of edges in a reduced graph of groups for
a context-free group, from which we derive our bounds.
Outline. After fixing our notation, we recall basic facts from Bass-Serre theory and
the results from [23] and give a short review on structure trees based on [9]. Section 3,
develops bounds on the size of the vertices (= equivalence classes of cuts) of the structure
tree. After that, we introduce virtually free presentations formally and we derive stronger
bounds for this case in Section 4. Section 5 completes the proofs of (A) and (B). Finally,
in Section 6 we derive (C) and (D) and we conclude with some open questions.

2 Preliminaries
Sets. In order to distinguish it from quotient groups, we write A r B for the difference
of sets A and B. Moreover, the cardinality of a set A is denoted by |A|.
Complexity. We use standard O-notation for functions from N to non-negative reals
R≥0 . We use the following convention for non-deterministic function problems: each
accepting computation path must yield a correct answer – though different accepting
paths can compute different correct answers. We use this convention to define the
classes NP (non-deterministic polynomial time) and NTIME(f (n)) (non-deterministic
time bounded by f (n)). Otherwise, we use standard complexity classes P (deterministic
1

Thus, (B) means that the graph of groups can be computed in NPMV in the sense of [21]. More precisely, it can be rephrased as follows: the multi-valued function mapping a virtually free presentation
for G into a pair (G, ϕ), where G is a graph of groups and ϕ : π1 (G) → G is an isomorphism of
polynomial size, is everywhere defined and belongs to the class FNP as defined in [20].

3

polynomial time), PSPACE (polynomial space) and DSPACE(f (n)) (deterministic space
bounded by f (n)) for both decision and function problems.
Words. An alphabet is a (finite) set Σ; an element a ∈ Σ is called a letter. The set Σn
forms the set of words of length n. The length of w ∈ Σn is denoted by |w|. The set
of all words is denoted by Σ∗ . It is the free monoid over Σ – its neutral element is the
empty word 1. If we can write w = uxv, then we call u a prefix, x a factor and v a suffix
of w.
Context-free grammars. We use standard notation for context-free grammars: a
context-free grammar, is a tuple G = (V, Σ, P, S) with variables V , terminals Σ,
productions rules PP⊆ V × (V ∪ Σ)∗ , and a start symbol S. We denote its size by
kGk = |V | + |Σ| + S→α∈P |α|. It is in Chomsky normal form if all production are of
the form S → 1, A → a or A → BC with A, B, C ∈ V , a ∈ Σ. For further definitions
on context-free grammars, we refer to [13].
Groups. We consider groups G together with a finite subset of monoid generators Σ.
Every word w ∈ Σ∗ is simultaneously viewed as the corresponding group element in G
under the canonical projection π : Σ∗ → G. Whenever it is not clear whether equality is
as group elements or words, we write w =G w′ as a shorthand of π(w) = π(w′ ). Thus,
w =G w′ means that w and w′ represent the same element in the group G. The word
problem of G is the formal language WP(G) = π −1 (1).
A symmetric set of generators is a set with the involution a 7→ a =G a−1 (i. e., a = a).
Let w ∈ Σ∗ and Σ be symmetric. We say that w is freely reduced if there is no factor
aa for any letter a ∈ Σ. Given an arbitrary set of generators X, the free group over X
is denoted by F (X). It is defined as (X ∪ X)∗ modulo the defining relations xx = 1 for
x ∈ X ∪ X.
Graphs. A (undirected) graph Γ = (V, E, s, t, · ) is given by the following data: A set
of vertices V = V (Γ), a set of edges E = E(Γ) together with two incidence maps
s : E → V and t : E → V and an involution E → E, e 7→ e without fixed points such
that s(e) = t(e). The vertex s(e) is the source of e and t(e) is the target of e. The degree
of u is the number of incident edges. A graph is finite, if it has finitely many vertices
and edges. An undirected edge is the set {e, e}. For the cardinality of sets of edges we
usually count the number of undirected edges. A directed graph is a graph without the
involution.
A (finite) path from v0 to vn is a pair of sequences ((v0 , . . . , vn ), (e1 , . . . , en )) such that
s(ei ) = vi−1 and t(ei ) = vi for all 1 ≤ i ≤ n. Similarly, a bi-infinite path is a pair of
sequences ((vi )i∈Z , (ei )i∈Z ) such that s(ei ) = vi−1 and t(ei ) = vi for all i ∈ Z. A path
is simple if the vertices are pairwise distinct. It is closed if v0 = vn . Depending on
the situation we also denote paths simply by the sequence of edges or the sequence of
vertices. Given two paths β and γ, we denote the concatenation by βγ. The distance
d(u, v) between vertices u and v is defined as the length (i. e., the number of edges) of a
shortest path connecting u and v. We let d(u, v) = ∞ if there is no such path. A path
v0 , . . . , vn is called geodesic if n = d(v0 , vn ). For A, B ⊆ V (Γ) the distance is defined as
d(A, B) = min { d(u, v) | u ∈ A, v ∈ B }. An undirected graph Γ is called connected if

4

d(u, v) < ∞ for all vertices u and v. A tree is a connected graph which does not contain
any non-trivial simple closed path.
For S ⊆ V (Γ) we define Γ − S to be the induced subgraph of Γ with vertices V (Γ) r S.
For C ⊆ V (Γ), we write C for the complement of C, i. e., C = V (Γ) r C. We call C
connected, if the induced subgraph is connected. A group G acts on a graph Γ, if it acts
on both V (Γ) and E(Γ) and the actions preserve the incidences.
Cayley graphs. Let G be a group and Σ a symmetric generating set of G. (If Σ is not
symmetric, we simply add a set of formal inverses Σ.) The Cayley graph Γ = ΓΣ (G) of
G (with respect to Σ) is defined by V (Γ) = G and E(Γ) = G × Σ, with the incidence
functions s(g, a) = g, t(g, a) = ga, and involution (g, a) = (ga, a−1 ). The Cayley graph
is connected because Σ generates G. The directed Cayley graph is defined analogously
without requiring that Σ is symmetric.
Cuts. For v ∈ V (Γ) let Bv (r) := { u ∈ V (Γ) | d(u, v) ≤ r } denote the ball with radius
r and center v. If Γ is a Cayley graph, we also write B(r) for the ball with radius r
and center 1. For a subset C ⊆ V (Γ) we define the edge and vertex boundaries of C as
follows:

~δC = e ∈ E(Γ) s(e) ∈ C, t(e) ∈ C = directed edge boundary,

δC = e ∈ E(Γ) s(e) ∈ C, t(e) ∈ C or t(e) ∈ C, s(e) ∈ C = edge boundary,

∂C = s(e) e ∈ ~δC = inner vertex boundary,

βC = s(e) e ∈ ~δC or e ∈ ~δC = ∂C ∪ ∂C = vertex boundary.
Definition 1. A cut is a subset C ⊆ V (Γ) such that C and C are both non-empty
and connected and δCis finite. The weight of a cut is |~δC|(so the weight of a cut is the
number of undirected edges in δC). If |~δC| ≤ k, we call C a k-cut. w

2.1 Bass-Serre theory
We give a brief summary of the basic definitions and results of Bass-Serre theory [24].
Definition 2 (Graph of Groups). Let Y = (V (Y ), E(Y )) be a connected graph. A
graph of groups G over Y is given by the following data:
(i) For each vertex P ∈ V (Y ) there is a vertex group GP .
(ii) For each edge y ∈ E(Y ) there is an edge group Gy such that Gy = Gy .
(iii) For each edge y ∈ E(Y ) there is an injective homomorphism from Gy to Gs(y) ,
which is denoted by a 7→ ay . The image of Gy in Gs(y) is denoted by Gyy .
Since we have Gy = Gy , there is also a homomorphism Gy → Gt(y) with a 7→ ay . The
image of Gy in Gt(y) is denoted by Gyy . A graph of groups is called reduced if Gyy 6= Gs(y)
whenever s(y) 6= t(y) for y ∈ E(Y ). Throughout we assume that all graphs of groups
are connected and finite (i. e., Y is a connected, finite graph).

5

Fundamental group of a graph of groups. We begin with the group F (G). It is defined
as the free product of the freegroup F (E(Y )) and the groups GP for P ∈ V (Y ) modulo
the set of defining relations yay y = ay U a ∈ Gy , y ∈ E(Y ) . As a set of (monoid)
generators we fix the disjoint union ∆ = P ∈V (Y ) (GP r {1}) ∪ E(Y ) throughout. Now,
we have

F (G) = F (∆)/ gh = [gh], yay y = ay P ∈ V (Y ), g, h ∈ GP ; y ∈ E(Y ), a ∈ Gy ,

where [gh] denotes the element obtained by multiplying g and h in GP .
For P ∈ V (Y ) we define a subgroup π1 (G, P ) of F (G) by the elements
g0 y1 · · · gn−1 yn gn ∈ F (G), such that y1 · · · yn is a closed path from P to P and
gi ∈ Gs(yi+1 ) for 0 ≤ i < n and gn ∈ GP . The group π1 (G, P ) is called the fundamental
group of G with respect to the base point P . Since we assumed Y to be connected,
there exists a spanning tree T = (V (Y ), E(T )) of Y . The fundamental group of G with
respect to T is defined as
π1 (G, T ) = F (G)/ { y = 1 | y ∈ T } .
Proposition 3 ([24]). The canonical homomorphism ψ from the subgroup π1 (G, P ) of
F (G) to the quotient group π1 (G, T ) is an isomorphism. In particular, the two definitions
of the fundamental group are independent of the choice of the base point or the spanning
tree.

A word w ∈ ∆∗ is called reduced if it does not contain a factor gh with g, h ∈ GP for
some P or a factor yay y with y ∈ E(Y ), a ∈ Gy .
Lemma 4 ([24, Thm. I.11]). A reduced word in π1 (G, P ) represents the trivial element
if and only if it is the empty word.
The quotient of a G-tree. Graphs of groups arise in a natural way in situations where a
group G acts (from the left) on some connected tree X = (V, E) without edge inversion,
i. e., e ∈
/ Ge for all e ∈ E. We let Y = G\X be the quotient graph with vertex
set V (Y ) = { Gv | v ∈ V } and edge set E(Y ) = { Ge | e ∈ E } and incidences and
involution induced by X. By choosing representatives we find embeddings ι : V (Y ) ֒→ V
and ι : E(Y ) ֒→ E and we can assume that ι(V (Y )) forms a connected subgraph of X
and that ι(y) = ι(y). For P ∈ V (Y ), y ∈ E(Y ), we define vertex and edge groups as
the stabilizers of the respective representatives: GP = Stab(ιP ) = { g ∈ G | gιP = ιP }
and Gy = Stab(ιy) = { g ∈ G | gιy = ιy }. Note that as abstract groups the vertex and
edge groups are independent of the choice of representatives since stabilizers in the same
orbit are conjugate. Moreover, for each y ∈ E(Y ), there are P, Q ∈ V (Y ) and gy , hy ∈ G
such that s(ιy) = gy ιP and t(ιy) = hy ιQ. Note that P and Q are uniquely determined by
y, whereas for gy and hy only the left cosets gy GP resp. hy GQ are uniquely determined.
Hence, here is another choice involved; still we can choose them such that gy = hy and
hy = gy . This yields two embeddings:
Gy → GP ,

a 7→ ay = g y agy ,

and

6

Gy → GQ ,

a 7→ ay = hy ahy .

(1)

Hence, we have obtained a well-defined graph of groups over Y . Notice that the Gyy
and Gyy depend on the choice of gy and hy (and change via conjugation when changing
them).
We define a homomorphism ϕ : ∆∗ → G by ϕ(g) = g for g ∈ GP , P ∈ V (Y ). For
y ∈ E(Y ), we set ϕ(y) = gy hy . That means ϕ(y) maps some edge in the preimage
of y and terminating in ιt(y) to an edge in the preimage of y with source in ιs(y).
By our assumption, we have ϕ(y) = hy gy = ϕ(y). Since ϕ(yay y) = ϕ(y)ϕ(ay )ϕ(y) =
hy gy ay g y hy = ay = ϕ(ay ), we obtain a well-defined homomorphism ϕ : F (G) → G.
Theorem 5 ([24]). The restriction ϕ : π1 (G, P ) → G is an isomorphism.

2.2 Context-free groups and graphs
In this section we recall some results from [17, 18, 22, 23].
Definition 6. A group is called context-free, if its word problem is a context free language.
Notice that the word problem of a context-free group is decidable in polynomial time –
even if the grammar is part of the input - by applying the CYK algorithm (see e. g. [13]).
Definition 7 (k-triangulable). Let Γ be a graph. Let k ∈ N and let γ = v0 , v1 , . . . , vn =
v0 be a sequence of vertices Γ such that d(vi−1 , vi ) ≤ k for all i ∈ { 1, . . . , n } (e. g. γ can
be a closed path). Let P a convex polygon in the plane whose vertices are labeled by the
vertices of γ (i.e. we consider γ as a simple closed curve in the plane). A k-triangulation
of γ is a triangulation of P which does not introduce any additional vertices (thus only
consists of “diagonal” edges) and such that vertices joined by a diagonal edge are are
distance at most k. We call the diagonal edges chords. A path witnessing that the end
vertices of the chord are at distance at most k is called a label of the chord. If n < 3,
we consider γ as triangulated.
If every closed path γ has a k-triangulation, then Γ is called k-triangulable.
Lemma 8 ([17, Thm. I]). Let (V, Σ, P, S) be a context-free grammar in Chomsky normal
form for the word problem of G where Σ is a symmetric generating set. Then the Cayley
graph Γ can be k-triangulated for k = 2|P | . Moreover, if Σ is not symmetric Γ can be
k-triangulated for k = 2|P |+2
Proof. Let (V, Σ, P, S) be a context-free grammar in Chomsky normal form for the word
problem of G and let Σ be symmetric. In [17] Muller and Schupp proved that Γ is
k-triangulable for some k. An easy induction shows that indeed k = 2|P | suffices.
In the case that Σ 6=G Σ−1 , the same holds but only for the directed Cayley-graph
′
Γ (at all nodes we have an outgoing directed edge for each letter in Σ), i.e. Γ′ can be
k′ -triangulated for some k′ = 2|P | . Now, for every a ∈ Σ we can take a shortest word
wa representing a−1 in G. By k′ -triangulability of Γ′ we have that wa has length at
most 3k′ (otherwise we could find a shortcut). Now, if we have a closed path γ in the
undirected Cayley-graph Γ, every edge of γ corresponds to a path of length at most 3k′

7

in Γ′ . The resulting path γ ′ in Γ′ can be k′ -triangulated. Since every vertex on γ ′ is at
5k ′
distance at most 3k
2 , this triangulation gives rise to a 2 k -triangulation of γ. Hence, Γ
′
is 4k -triangulable.
Remark 9. From now on we always assume that Σ is symmetric. As the previous
lemma shows this gives only a linear blow-up to the triangulation constant k.
Lemma 10 ([18, p.65]). Let Γ be k-triangulable and let r ∈ N. If C is a connected
component of Γ − B(r), then diam(∂C) ≤ 3k.
Lemma 11. Let Γ be connected and k-triangulable and let C ⊆ V (Γ) be a cut. Then
~
diam(βC) ≤ 3k
2 |δC|.
This lemma is asserted (without proof) in [22, Lemma 6] with a slightly worse bound
on diam(βC).
Proof. We show that for every v0 ∈ βC we have

 

3k ~
|δC| − 1 + 1 .
βC ⊆ Bv0
2
More precisely, we will inductively construct an enumeration ~δC = { e0 , . . . , en } for
n = |~δC| − 1 such that v0 is an endpoint of e0 and d(v0 , t(ei )), d(v0 , s(ei )) ≤ i·3k
2 + 1 for
i > 0.
δC
u
C

C
f 6∈ Ei
ei ∈ Ei

γ

e ∈ Ei

v0

e0

Figure 1: A shortest path γ from v0 to u. We have e ∈ Ei = { e0 , e0 . . . , ei , ei } and
f ∈ δC r Ei
Let e0 be an edge with endpoint v0 . Then both endpoints of e0 have distance at most
one to v0 .
Let { e0 , . . . , ei } be constructed for some i < n. Now let u ∈ βC be a vertex which is
not an endpoint of an edge in { e0 , . . . , ei } and take a shortest path γ from v0 to u in Γ.

8

f
..
.
ei+1
γ′

γ ′′
ej
..
.
e

Figure 2: There is one triangle with one side containing an edge ej ∈ { e0 , e0 . . . , ei , ei }
and one side containing an edge from δC r{ e0 , e0 . . . , ei , ei }. This second edge
is the new edge ei+1 .
We denote Ei = { e0 , e0 . . . , ei , ei }. Let e be the last edge on γ from Ei and let f the
next edge on γ belonging to δC (i. e., f ∈ δC r Ei ) – see Figure 1.
Let γ ′ be the subpath of γ connecting t(e) to s(f ) – i. e., γ ′ is a shortest path from t(e)
to s(f ). W. l. o. g. we may assume that γ ′ is contained in C. Since also C is connected,
there is also a path γ ′′ from t(f ) to s(e) inside C.
The closed path γ ′ f γ ′′ e can be k-triangulated. If γ ′ and γ ′′ are of length zero, we take
ei+1 = f and we are done by induction. Otherwise, there must be at least one triangle
having two vertices in γ ′ and one in γ ′′ or vice-versa. Moreover, all the triangles of this
form build a linearly ordered chain where on one end there is one triangle with a side
labeled by e and on the other end a triangle labeled by f . Now, all these triangles have
two sides which correspond to paths crossing δC – hence these paths all contain an edge
of δC. Now consider the last triangle such that one side (and only one side) contains an
edge from Ei – lets say ej – and one edge from δC r Ei . The latter edge (in its correct
orientation) is the new edge ei+1 . Now, the length of the three sides of the triangle
together is at most 3k. Therefore, the distance between any two vertices in any of the
sides is at most 3k/2. In particular,
max { d(u, v) | u ∈ {s(ej ), t(ej )} , v ∈ {s(ei+1 ), t(ei+1 )} } ≤

3k
2

and we are done by induction.
The following upper-bounds will be useful.
Proposition 12 ([23, Prop. 1.2]). Let Γ be the Cayley graph on X ∪ X of a group G
and let us suppose that Γ is k-triangulable. Let H ≤ G be a finite subgroup. Then
|H| ≤ (2 · |X|)12k+10 .
Theorem 13 ([23, Thm. 1.4]). Let Γ be the Cayley graph on X of a group G and let us
suppose that Γ is k-triangulable. Then every minimal graph of groups G admitting G as
fundamental group has at most (2 · |X|)12k+11 undirected edges.

9

2.3 Optimal cuts and structure trees
We briefly present the construction of optimal cuts and the associated structure tree
from [9, 10]. While in [9], the proof was for arbitrary accessible co-compact and locally
finite graphs, here we assume that Γ is the Cayley graph of a context-free group. We are
interested in bi-infinite simple paths which can be split into two infinite pieces by some
cut. For a bi-infinite simple path α denote:

C(α) = C ⊆ V (Γ) C is a cut and |α ∩ C| = ∞ = α ∩ C ,
Cmin (α) = { C ∈ C(α) | |δC| is minimal in C(α) } ,

where we identify α with its set of vertices. If C(α) 6= ∅, we say that C splits α. We
define the set of minimal cuts Cmin as the union over the Cmin (α) for all all bi-infinite
simple paths α. Note that Cmin may contain cuts of very different weight. Actually we
might have C, D ∈ C(α) ∩ Cmin with C ∈ Cmin (α), but D ∈
/ Cmin (α). In such a case there
must be another bi-infinite simple path β with D ∈ C(α) ∩ Cmin (β) and |δC| < |δD|.
For example, let Γ be the subgraph of the infinite grid Z × Z which is induced by the
pairs (i, j) satisfying j ∈ {0, 1} or i = 0 and j ≥ 0. Let α be the bi-infinite simple path
with i = 0 or j = 1 and i ≥ 0 and let β be the bi-infinite simple path defined by j = 0.
Then there are such cuts with |δC| = 1 and |δD| = 2, as depicted in Figure 3.
..
.

δC

δD

···

α
···

(0, 0)

β

Figure 3: The subgraph of the grid Z × Z induced by the pairs (i, j) satisfying j ∈ {0, 1}
or i = 0 and j ≥ 0. Here we have D ∈ C(α) ∩ Cmin but D ∈
/ Cmin (α).
Let us prove some bounds on weight and diameter of minimal cuts:
Lemma 14. Let Γ be k-triangulable and let d denote the degree of Γ. Then for every
C ∈ Cmin we have
(i) |~δC| ≤ d3k+2 and
(ii) diam(βC) ≤

3k 3k+2
.
2 d

Proof. Let C be a connected component of Γ − B(m) for any m ∈ N. By Lemma 10 we
Pdiam(∂C) i
have diam(∂C) ≤ 3k. Hence, |~δC| ≤ i=1
d ≤ d3k+2 . Since any bi-infinite path
10

which can be split by some cut into two infinite paths also can be split into two infinite
part by a cut which is a connected component of Γ − B(m) for some m ∈ N (just make m
large enough that the boundary of the cut splitting the path lies entirely within B(m)),
we know that |~δC| ≤ d3k+2 also for every minimal cut C. By Lemma 11 it follows that
3k 3k+2
~
diam(βC) ≤ 3k
for every minimal cut C.
2 |δC| ≤ 2 d
Two cuts C and D are called nested, if one of the four inclusions C ⊆ D, C ⊆ D,
C ⊆ D or C ⊆ D holds. By Lemma 14, with K = d3k+3 for every bi-infinite simple path
α with C(α) 6= ∅ there exists some cut C ∈ C(α) with |~δC| ≤ K. We fix this number
K. For a cut C let m(C) denote the number of K-cuts that are not nested with C. It
follows from [25] that m(C) is always finite, see also [9, Lem. 3.4]. This allows us to
define the set of optimal cuts:
Copt (α) = { C ∈ Cmin (α) | m(C) ≤ m(D) for all D ∈ Cmin (α) } ,
[
Copt =
{ Copt (α) | α is a bi-infinite simple path } .

Definition 15. A set C ⊆ C(Γ) of cuts is called a tree set, if C is pairwise nested, closed
under complementation and for each C, D ∈ C the set { E ∈ C | C ⊆ E ⊆ D } is finite.
Proposition 16 ([9]). Copt is a tree set.
Definition 17. Let C be a tree set. We can now define the following relation:
C ∼ D :⇐⇒ C = D or (C $ D and E ∈ C, C $ E ⊆ D =⇒ E = D).
Indeed, ∼ is an equivalence relation – see e. g. [8]. The intuition behind this definition
is: We consider C as edge set of a graph, and define two edges to be incident to the same
vertex, if no other edge lies “between” them.
Definition 18. Let C be a tree set and let T (C) denote the graph defined by
V (T (C)) = { [C] | C ∈ C } ,

E(T (C)) = C.

The incidence maps are defined by s(C) = [C] and t(C) = [C]. The involution C
is defined by the complementation C = V (Γ) r C; hence, we do not need to change
notation.
The directed edges are in canonical bijection with the pairs ([C], [C]). Indeed, let
C ∼ D and C ∼ D. It follows C = D because otherwise C $ D $ C. Thus, T (C) is an
undirected graph without self-loops and multi-edges. Indeed, T (C) is a tree [8].
Theorem 19 ([9, Thm. 5.9]). Let Γ be a connected, k-triangulable, locally finite graph.
Let a group G act on Γ such that G\Γ is finite and each node stabilizer Gv is finite.
Then G acts on the tree T (Copt ) such that all vertex and edge stabilizers are finite and
G\T (Copt ) is finite.

11

3 Bounds on the structure tree
In order to prove our main result, we have to show that there exists a “small” graph of
groups together with a “small” isomorphism. For constructing such a graph of groups,
we start with the structure tree and bound the size of the equivalence classes and the
diameter of the boundaries of the cuts in one equivalence class. As before Γ is the Cayley
graph of a context-free group G.
Complete cut sets. By Proposition 16 and Theorem 19, Copt is a tree set of cuts
on which G acts with finitely many orbits such that the vertex stabilizers G[C] =
{ g ∈ G | gC ∼ C } of the structure tree are finite. We call a set of cuts with these
properties a complete cut set.
Avoiding edge inversion. We aim to construct a graph of groups as described in Section 2.1 from the structure tree T (Copt ). However, if the action of G on T (Copt ) is with
edge inversion, the construction cannot be applied directly. Instead, we switch to a
subdivision Te(C) of T (C) by putting a new vertex in the middle of every edge which is
inverted (in particular, V (T (C)) ⊆ V (Te(C))). Formally, Te(C) is defined as follows: for
every edge C of T (Copt ) with gC = C we remove C and C and instead add a new vertex
v{C,C} together with edges C1 , C 1 , C2 , C 2 with gC1 = C 2 , gC2 = C 1 and s(C1 ) = [C],
t(C1 ) = v{C,C} , s(C2 ) = v{C,C} , and t(C2 ) = [C].
Reduced cut sets. Given a complete cut set C, we obtain a graph of groups with
finite vertex groups by taking the quotient G\Te(C) with the procedure from Section 2.1.
We aim to apply Theorem 13, to bound the number of edges in this graph of groups.
However, the graph of groups might not be reduced. In terms of the structure tree T (C)
this means that there are either vertices [C] and [C] which are not in the same G-orbit
and G[C] = GC or that G[C] = GC and there is some g ∈ G with gC = C. Nevertheless,
in this case we can switch to a subset Ce ⊆ C such that still all vertex stabilizers are
finite and the corresponding graph of groups
is reduced: if there is some cut C ∈ C

with G[C] = GC and either [C] 6∈ G · [C] or C ∈ G · {C}, then we can replace C

by C r G · C, C (in terms of the structure tree this means we collapse the respective
edges). If there is no such C ∈ C anymore, we have obtained a reduced set of cuts C.
The following lemmas are straightforward to verify.
Lemma 20. Let C be a complete cut set and let C ′ be the reduced cut set obtained by the
above procedure. Then C ′ is also complete (i. e., all vertex stabilizers are still finite).
Proof. We only need to proof that still all vertex stabilizers (or equivalently all equivalence classes – since G acts freely on Γ) are finite. Consider the structure tree T (C). If
we remove some cut from C it
 means we collapse the respective edge.
Let C ∈ C with [C] 6∈ G · [C] and G[C] = GC and consider the set of cuts C r G ·

C, C . Thus, [C] ∩ G · {C} = {C}. Let P the vertex in the structure tree with C ∈ P .

12


Removing G · C, C amounts to replacing P = [C] by


[
[ 
P ′ = [C] ∪
gC, gC
g[C] r
g∈GP

,

g∈GP

which is also finite.
Now, let C ∈ C with C ∈ G·{C} and G[C] = GC and consider the cut set C rG·{C} =



C r G · C, C . Then we have [C] ∩ G · {C} = {C} and [C] ∩ G · C = C . Let P
the vertex in the structuretree with C ∈ P . Removing G · {C} amounts to replacing
P = [C] by P ′ = [C] ∪ [C] r C, C , which again is finite.

Lemma 21. Let C be a reduced cut set and let Te(C) be the associated structure tree
without edge inversion. Then the graph of group built on G\Te(C) is reduced.

Proof. Let G be a graph of groups over Y and let ι : V (Y ) → V (Te(C)) and ι : E(Y ) →
E(Te(C)) be the choice of representative as in Section 2.1. Assume that G is not reduced,
i. e., there is an edge y ∈ E(Y ) with Gyy = Gs(y) and t(y) 6= s(y). Then ιs(y) ∈ V (T (C))
(i. e., s(y) is not in the orbit of one of the additional vertices introduced on inverted
edges) because otherwise the index of Gyy in Gs(y) would be two. We distinguish the two
cases that ιt(y) is one of these special vertices and one of the
 original vertices of T (C).
If ιt(y) is in T (C), then ιy = C for some C ∈ C and [C] 6∈ G · [C] and GC = G[C] , i. e.,
C is not reduced.
On the other hand, let ιt(y) = v{C,C} for some C ∈ C. Then by the construction of
Te(C), we have C ∈ G · {C}. Since by assumption GC = G[C] , that means again that C
is not reduced.

Let Ξ be an upper bound on the order of finite subgroups of G and let Θ be a bound
on the number of undirected edges in a reduced graph of groups for G. Notice that by
Proposition 12, we have Ξ ≤ d12k+10 and by Theorem 13 we have Θ ≤ d12k+11 where k
is the triangulation constant and d the degree of Γ.
Lemma 22. Let C be a reduced complete set of cuts and let C ∼ D ∈ C. Then
(i) |{ g ∈ G | gD ∼ C }| ≤ Ξ, and
(ii) |[C]| ≤ 2 · Θ · Ξ.
Proof. Let g ∈ G with gD ∼ C and let E ∈ [C]. Then, gE ∼ gC ∼ gD ∼ C. Thus,
gE ∈ [C] and so g ∈ G[C] . By Theorem 19, G[C] is finite; thus, its size is bounded by Ξ.
This shows the first point.
For the second bound observe that, by the definition of Θ and by Lemma 21, there are
at most 2Θ different G-orbits of (directed) edges of Te(C) (the 2 comes from the fact Θ
counts undirected edges). Recall that Te(C) originated from T (C) by adding new vertices
in the middle of edges C with gC = C for some g ∈ G. Thus, adding new vertices on
these edges does not change the number of G-orbits of edges. Hence, |G\C| ≤ 2Θ. Now,
by the first point, for every G-orbit there are at most Ξ cuts in [C].

13

Lemma 23. Let C be a tree set of cuts and let G act on C. Let C ∈ C and
S C ∈ P ⊆ [C].
Then P 6= [C] if, and only if, there is some E ∈ [C] r P with d(∂E, D∈P ∂D) ≤ 1.

Proof. The if-part is clear. Thus, let P 6= [C].
T Then there is some ES∈ [C] r P . Since
E $ D for all D ∈ P , we have ∅ =
6 E ⊆ D∈P
⊆ D∈P ∂D, we are
T D. Now, if ∂E S
E
⊆
D
with
d(u,
done. Otherwise, there is some vertex
u
∈
D∈P
D∈P ∂D)
T
S ≥ 1. Take
the connected component F of D∈P D such that u ∈ F . Since ∂F ⊆ D∈P ∂D (if
w ∈ ∂F ,Tthen w is adjacent
S to some vertex in D for some D ∈ P ), we find a vertex
v ∈ F ⊆ D∈P D with d(v, D∈P ∂D) = 1. Notice that, in particular, we have
v 6∈ βD ∪ D

for all D ∈ P.

(2)

e ∈ C such that v ∈ β E.
e After
Now since Γ is vertex-transitive, we can find some cut E
e with its complement, we can assume that E
e $ C or E
e ⊆ C.
possibly exchanging E
e
The latter would imply v ∈ β E ⊆ βC ∪ C contradicting (2). Moreover, for any other
e ⊆ D because all other possibilities for E
e and D being nested lead to
D ∈ P , we have E
a contradiction:
e then D $ E
e $ C contradicting D ∼ C
• if D $ E,

e then D ⊆ E
e ⊆ C and D ⊆ C contradicting C 6= ∅
• if D $ E,

e ⊆ βD ∪ D contradicting (2).
e ⊆ D, then v ∈ β E
• if E
e ⊆T
e
Thus, E
D∈P D. Let E ∈ C be minimal with respect to inclusion such that E ⊆
e ⊆ βE ∪ E.
E $ C. Then E ∼ C, but E 6∈ P S
because v ∈ β E
It remains to verify that d(∂E, D∈P ∂D) ≤ 1. Let w ∈ ∂D for some D ∈ P a vertex
with d(w, v) = 1. Then, we have w ∈ βD ∪ D ⊆ βE ∪ E. Consider
the two cases: v ∈ E
S
and v ∈ ∂E.S If v ∈ E, then w ∈ βE ∩ ∂D and hence d(∂E, D∈P ∂D) ≤ 1. If v ∈ ∂E,
then d(∂E, D∈P ∂D) ≤ d(v, w) = 1.
Lemma 24. Let C be a complete set of cuts and R ∈ N such that diamβC ≤ R for all
C ∈ C. Let C ∈ C, then
!
[
diam
βC ≤ (R + 1) · |[C]| .
C∼D

Proof. We can construct the class [C] by starting with the singleton set { C } and successively adding cuts D with D ∼ C. More precisely, we construct a sequence of cuts
C1 , . . . , Cn such that C1 = C, Ci ∼ C for all i and βCi ⊆ Bv ((R + 1)i) for any fixed
v ∈ βC. This will show the lemma.
By assumption, we have βC1 ⊆ Bv (R). Now, let C1 , . . . , Ci S
be constructed. If
{ C1 , . . . , Ci } =
6 [C], by Lemma 23, we find a cut Ci+1 ∈ [C] with d( ij=1 ∂Cj , ∂Ci+1 ) ≤
1. Thus, by induction d(v, ∂Ci+1 ) ≤ 1 + (R + 1)i and so βCi+1 ⊆ Bv ((R + 1)(i + 1)).
Lemma 25. Let Γ be the Cayley graph of G. Moreover, assume that

14

• R is an upper bound on the diameter of the boundary of minimal cuts,
• Θ is an upper bound on the number of undirected edges of a reduced graph of group
for G,
• Ξ is an upper bound on the size of finite subgroups of G.
Then there exists a graph of groups G over Y and an isomorphism ϕ : π1 (G, T ) → G
with
(i) |V (Y )| ≤ Θ + 1,
(ii) |GP | ≤ Ξ for all P ∈ V (Y ),
(iii) |ϕ(a)| ≤ 4(R + 1) · (Θ + 1)2 · Ξ for every a ∈

S

P ∈V (Y ) GP

∪ E(Y ).

Proof. First consider the case that Γ is finite. In this case we have V (Y ) = { P } with
G∼
= GP . Thus, |V (Y )| = 1 ≤ Θ + 1 and |GP | ≤ Ξ by definition of Ξ. Moreover, the
Cayley graph of G has diameter at most Ξ − 1 (as it has only Ξ vertices). Therefore,
every every g ∈ GP has an image of length at most Ξ − 1 ≤ 2(R + 1) · (Θ + 1)2 · Ξ.
Now let Γ be infinite. We start with the structure tree T (Copt ). By Lemma 20, we
can switch to a complete subset C ⊆ Copt such that the corresponding graph of groups
is reduced. Let Y = G\Te(C) (as described at the beginning of Section 3, Te(C) is the
tree obtained from T (C) by putting additional vertices on inverted edges). We need to
choose proper representatives ιV (Y ) and ιE(Y ) to construct the graph of groups as in
Section 2.1.
S
Fix any P ∈ V (Y ) and choose a representative ιP ∈ V (Te(C)) such that 1 ∈ C∈ιP ∂C.
Now, choose the other representatives according to Section 2.1 such that ιV (Y ) forms
a connected subgraph and ιE(Y ) is closed under complementation. This defines the
vertex and edge groups as the respective stabilizers. For vertices Q with ιQ = v{C,C}
(i. e., vertices placed on inverted edges), the vertex group is the stabilizer Gv{C,C} =

g ∈ G gC = C or gC = C . For the edge y with s(y) = Q, we set Gy = GC if
C ∈ ιP for some P ∈ V (Y ) r {Q} (i. e., C is the cut which connects v{C,C} to the rest
of ιV (Y )).
Now, y ∈ E(Y ) is incident to P ∈ V (Y ) if, and only if, s(ιy) = gy ιP for some gy ∈ G
(resp. t(ιy) = gy ιP ). For every y ∈ E(Y ) we can fix such an element gy and define
ϕ : F (G) → G by
ϕ(g) = g

for g ∈ GP , P ∈ V (Y ),

ϕ(y) = gy−1 gy

for y ∈ E(Y ).

By Theorem 5 this induces an isomorphism π1 (G, T ) → G.
Points (i) and (ii) hold by the very definition of Θ and Ξ (since Y is connected, it has
at least |V (Y )| − 1 edges). For point (iii), let us first show that
[ [
∂D ⊆ B(2(R + 1) · (Θ + 1) · Θ · Ξ + Θ).
(3)
P ∈V (Y ) D∈P

15

For S
every equivalence
class P ∈ V (Y ), by Lemma 24 and Lemma 22, we have

diam D∈P ∂D ≤ (R + 1) 
· 2 · Θ · Ξ. Moreover, by (i), we have |V (Y )| ≤ Θ + 1.
S
S
Since d
D∈P ∂D, D∈Q ∂D ≤ 1 if there is an edge (i. e., a cut) connecting P to Q,
we obtain (3). Let us write Λ for 2(R + 1) · (Θ + 1) · Θ · Ξ + Θ.
Now, consider the action of G on its Cayley graph Γ: every g ∈ GP for S
P ∈ V (Y )
maps a vertex from B(Λ) to another vertex in B(Λ) (namely the elements of D∈P ∂D).
Since the action of G on Γ is free, this means that g has length at most 2Λ. Likewise
−1
gD of an edge D ∈ P with P ∈ V (Y ) – that is in particular ∂D ⊆ B(Λ) –
the image gD
maps ∂D ⊆ B(Λ + 1) into B(Λ) (since it maps the class [D] into V (P )). Therefore,
|ϕ(D)| ≤ 2Λ + 1 = 2 (2(R + 1) · (Θ + 1) · Θ · Ξ + Θ) + 1
≤ 4(R + 1) · (Θ + 1)2 · Ξ.

4 Stronger bounds for virtually free presentations
Let us start with a virtually free group G given as a free subgroup F (X) of finite index
together with a system of representatives S of F \G. That means every group element
can be written as xs with x ∈ F (X) and s ∈ S. Moreover, this normal form can be
computed in linear time from an arbitrary word by successively applying “commutation
rules” of letters from S and X∪X∪S to the word. This gives a virtually free presentation.
For this special case, we can derive stronger bounds on the triangulation constant k and
other parameters. These can be used later to show that in this case the graph of groups
can be computed in NP.
Formally, a virtually free presentation V for G is given by the following data:
• finite sets X, X, S, where X∪X is a symmetric alphabet, 1 ∈ S and (X∪X)∩S = ∅,
• for all y ∈ X ∪ X, r, t ∈ S r {1}, there are words xr,y , xr,t ∈ (X ∪ X)∗ , sr,y , sr,t ∈ S
such that
ry =G xr,y sr,y

rt =G xr,t sr,t

(4)

fulfilling two properties:
(i) for all r ∈ S r {1} there is some r ′ ∈ S r {1} such that sr′ ,r = 1 (i. e., G is a group),
(ii) the equations (4), oriented from left to right, together with the free reductions
xx = 1 for x ∈ X ∪ X form a confluent rewriting system (for a definition, see e. g.
[3, 14]).
Clearly such a presentation is terminating (noetherian), F (X) is a subgroup of G, G =
F (X) · S, and F (X) ∩ S = {1} (hence S is a system of right-representatives for F (X)).
Note that properties (i) and (ii) can be checked in polynomial time.
Using this confluent rewriting system, every g ∈ G can be uniquely written in its
normal form g = xs where x ∈ (X ∪ X)∗ is a freely reduced word and s ∈ S. Given

16

any word in (X ∪ X ∪ S)∗ , the normal form can be computed in linear time from left
to right by applying the identities (4) and reducing freely. This is the computation of a
deterministic pushdown automaton for the word problem of G:
Lemma 26. Let G be the group defined by a virtually free presentation V. Then a
deterministic pushdown automaton for WP(G) can be computed in polynomial time.
Notice that a finite extension of a free group is a special case of a virtually free
presentation where F (X) is a normal subgroup of G (i. e., sr,y = r for all r ∈ S, y ∈
X ∪ X).
We assume that V is written down in a naive way as input for algorithms: there is a table which for all a ∈ X ∪X ∪S and r ∈ S contains aword xr,a and some sr,a ∈ S. The size
(number of letters) of this table is S ·(2X +S)·max |xr,a | + 1 a ∈ X ∪ X ∪ S, r ∈ S .
Up to logarithmic factors, this is the number of bits required to write down V this way.
We can always add a disjoint copy of formal inverses S of S representing S −1 in
G. Note that for s ∈ S this yields the rule
 rs = xr,s , sr,s for some sr,s ∈ S and with
xr,s = x−1
.
In
particular,
|x
|
≤
max
|xr,a | a ∈ X ∪ X ∪ S, r ∈ S . Therefore,
r,s
sr,s ,s

we define the size of V as kVk = S(2X + 2S) · max |xr,a | + 1 a ∈ X ∪ X ∪ S, r ∈ S .
Whenever we talk about a group G given as a virtually free presentation, we denote
Σ = X ∪ X ∪ S ∪ S. The respective Cayley graph Γ = ΓΣ (G) – as it is undirected – is
defined with respect to this alphabet. So in particular, its degree is bounded by kVk.
Lemma 27. Let T be a tree and let v0 , . . . , vn a sequence of vertices of T such that
v0 = vn and d(vi , vi−1 ) ≤ k for some k ∈ N. Then, the sequence v0 , . . . , vn is ktriangulable.
Proof. Let i be such that d(vi , v0 ) is maximal. We will show that the sequence
u0 , . . . , un−1 with uj = vj for j < i and uj = vj+1 for j ≥ i still satisfies d(ui , ui−1 ) ≤ k.
Then the lemma follows by induction.
In particular, we only need to show that d(vi−1 , vi+1 ) ≤ k. Let x be the last vertex
which is shared by the geodesics from v0 to vi and to vi−1 and y the last vertex shared
by the geodesics from v0 to vi and to vi+1 . Without loss of generality we may assume
d(v0 , x) ≤ d(v0 , y) meaning that d(x, vi ) = d(x, y) + d(y, vi ) and d(x, vi+1 ) = d(x, y) +
d(y, vi+1 ).
Since d(v0 , vi ) is maximal, we have d(y, vi+1 ) ≤ d(y, vi ). Moreover, by the assumption
of the lemma, we have d(vi−1 , vi ) = d(vi−1 , x) + d(x, vi ) ≤ k. Therefore,
d(vi−1 , vi+1 ) ≤ d(vi−1 , x) + d(x, vi+1 )
= d(vi−1 , x) + d(x, y) + d(y, vi+1 )
≤ d(vi−1 , x) + d(x, y) + d(y, vi )
= (vi−1 , x) + d(x, vi ) = d(vi−1 , vi ) ≤ k
Lemma 28. Let G be the group defined by a virtually free presentation V and let Γ be
its Cayley graph. Then Γ is k-triangulable for k = 2 kVk + 2.

17

Proof. Consider a closed path v0 , . . . , vn (i. e., for all i there is some a ∈ Σ with vi =
vi−1 · a and vn = v0 ) and let xi si for xi ∈ F (X), si ∈ S be the normal form of vi for
i = 0, . . . , n. We consider the sequence x0 , . . . , xn in the Cayley graph of F (X). Since
xi si = xi−1 si−1 a for some a ∈ Σ, we have
xi = xi−1 si−1 as−1
= xi−1 xsi−1 ,a ssi−1 ,a si = xi−1 xsi−1 ,a xssi−1 ,a ,si sssi−1 ,a ,si .
i

Therefore, we have d(xi , xi+1 ) ≤ 2 max |xr,a | + 1 a ∈ X ∪ X ∪ S, r ∈ S ≤ 2 kVk
and so the sequence x0 , . . . , xn can be 2 kVk-triangulated by Lemma 27. Now such a
2 kVk-triangulation is a 2 kVk + 2-triangulation of the original path v0 , . . . , vn .
Lemma 29. Let G be the group defined by a virtually free presentation V. Then for
every finite subgroup H ≤ G, we have |H| ≤ |S|. Hence, in particular, |H| ≤ kVk.
Proof. The group G acts on the quotient F (X)\G from the right with stabilizers being
conjugates of F (X). Since H is finite, it has trivial intersection with any conjugate of
F (X) and so it acts freely on F (X)\G. Thus, there is an injective map H → F (X)\G.
Since S is a system of representatives of F (X)\G, it follows |H| ≤ |S| ≤ kVk.
Lemma 30. Let G be the group defined by a virtually free presentation V. Then the
number of edges of a reduced graph of groups for G with finite vertex groups is at most
kVk.
Proof. The proof is analogous to [23, Thm. 1.4]: by [16, Thm. 2], we have
2(X + S) ≥ 1 +

X 1
|Ge |

e∈E

where E are the undirected edges of the graph of groups and Ge the respective edge
groups (note that here every undirected edge { e, e } is counted only once). Since all
edge groups are finite, we obtain
|E| ≤ 2(X + S) · max |Ge |
e∈E

≤ 2(X + S) · |S|

(by Lemma 29)

≤ kVk .
Lemma 31. Let G be the group defined by a virtually free presentation V and let Γ be
its Cayley graph. Then every minimal cut in Γ is a K-cut for K = kVk2 .
Proof. Consider the set of normal forms: every group element g ∈ G can be written as
xg sg for a unique freely reduced word xg ∈ (X ∪ X)∗ and sg ∈ S. Given some freely
reduced x ∈ (X ∪ X)∗ , it defines a cut Cx = { ys | s ∈ S, x is a prefix of y } (clearly Cx
and C x are connected – below we prove that ~δCx is finite). Notice that every bi-infinite
simple path in Γ which can be split by any cut also can be split by some cut of the form
Cx . Hence, it remains to bound ~δCx .

18

Consider some (yr, a) ∈ ~δCx , i. e., yr ∈ Cx and yra =G zs ∈ C x for a ∈ X ∪ X ∪ S ∪ S,
y, z ∈ (X ∪ X)∗ and r, s ∈ S. Thus, we have zxs,a =F (X) y. Since z, xs,a and y are freely
reduced, there are freely reduced v, z ′ , x′s,a ∈ (X ∪ X)∗ such that z = z ′ v and xs,a = vx′s,a
and y = z ′ x′s,a as words. Since x is a prefix of y but not of z, it follows that x is a prefix
of z ′ x′s,a but not of z ′ .
Hence, if we fix x′s,a, then there are at most x′s,a many possibilities for z ′ (namely
the prefixes of z ′ of length |z ′ | − i for i = 1, . . . , x′s,a ). Moreover, if we fix only a and
P|xs,a |
s, then x′s,a can be any suffix of xs,a . Thus, there are at most i=1
i ≤ |xs,a|2 many
possibilities for z ′ if a and s are known. Knowing x′s,a , xs,a , and z ′ determines also z
and y completely. Thus, summing up over all different a and s, we obtain
X
X
|~δCx | ≤
|xs,a |2 ≤ |S| · X ∪ X ∪ S ∪ S · max |xs,a|2 ≤ kVk2 .
s∈S
a∈X∪X∪S∪S

s∈S a∈X∪X∪S∪S

5 Main results: computing graphs of groups
Lemma 32. The uniform rational subset membership problem for virtually free groups
given as virtually free presentation or as context-free grammar for the word problem can
be decided in polynomial time. More precisely, the input is given as
• either a virtually free presentation V or a context-free grammar G = (V, Σ, P, S)
for the word problem of a group G,
• a rational subset of G given as non-deterministic finite automaton or regular expression over Σ (in the case of a virtually free presentation Σ is defined as in
Section 4),
• a word w ∈ Σ∗ .
The question is whether w is contained in the rational subset of G.
Proof. For this proof we will distinguish between group elements and words. Let p :
Σ∗ → G denote the canonical projection. Since a regular expression can be transformed
into a finite automaton with only linear overhead (see e. g. [13]), we can assume that the
input is given as a non-deterministic finite automaton accepting the regular language
L ⊆ Σ∗ . The question now is whether p(w) ∈ p(L).
From this automaton, we construct a new automaton for L′ = wL by adding |w| new
states. Clearly, p(w) ∈ p(L) if, and only if, 1 ∈ p(L′ ) or with other words p−1 (1)∩L′ 6= ∅.
The latter can be tested by computing a pushdown-automaton for p−1 (1) – either with
the standard construction from a context-free grammar [13] or from the virtually free
presentation as in [17]. Both constructions can be done in polynomial time. From this
push-down automaton we can easily construct a new pushdown-automaton for p−1 (1) ∩
L′ , which then can be checked for emptiness (for both constructions see [13]).
Proposition 33. The following problem is in P: Given a virtually free group G either
as virtually free presentation V or as context-free grammar G for its word problem and a

19

graph of groups G over the graph Y (with vertex groups as multiplication tables, i. e., for
all g, h ∈ GP the product S
gh is written down explicitly) together with a homomorphism
ϕ : ∆∗ → Σ∗ (where ∆ = P ∈V (Y ) GP ∪ E(Y ) and Σ is the generating set for G defined
by V (resp. G)), decide whether ϕ induces an isomorphism π1 (G, T ) → G.
Proof. We verify that ϕ induces a homomorphism ϕ̃ : π1 (G, T ) → G and that ϕ̃ is
injective and surjective.
Testing that ϕ really induces a homomorphism reduces to the word problem for the
group G, which can be solved in polynomial time: for every relation a1 · · · am = 1 of
π1 (G, T ) test whether ϕ(a1 ) · · · ϕ(am ) = 1 in G. Testing that ϕ̃ is surjective reduces to
polynomially many membership-problems for rational subsets of G: for all a ∈ Σ test
whether a is contained in the rational subset { ϕ̃(g) | g ∈ ∆ }∗ . By Lemma 32 this can
be done in polynomial time.
It remains to test whether ϕ̃ is injective. Let π : ∆∗ → F (G) and F (G) → π1 (G, T )
∼
denote the canonical projections (note that ψ induces an isomorphism π1 (G, P ) −→
π1 (G, T )). Let R ⊆ ∆∗ denote the set of reduced words. With slight abuse of notation
we use π1 (G, P ) also to denote the set of words g0 y1 · · · gn−1 yn gn ∈ ∆∗ where y1 · · · yn is
a closed path based at P and gi ∈ Gs(yi+1 ) for 0 ≤ i < n and gn ∈ GP . Testing that ϕ̃
is injective amounts to test whether the language

L = π −1 (ψ −1 (ϕ̃−1 (1))) ∩ π1 (G, P ) ∩ R r {1} ⊆ ∆∗

is empty because 1 is the only reduced word in π1 (G, P ) representing the identity, by
Lemma 4.
Notice that π −1 (ψ −1 (ϕ̃−1 (1))) = ϕ−1 (WP(G)). Since WP(G) is context-free (for
virtually free presentations, see Lemma 26) and since context-free languages are closed
under inverse homomorphism, ϕ−1 (WP(G)) is a context-free language – and a pushdown
automaton for it can be computed in polynomial time from the pushdown automaton
for WP(G) (see [13]).
Both π1 (G, P ) and R are regular languages with finite automata of size polynomial
in the size of the graph of groups (and they can be computed in polynomial time): For
π1 (G, P ) take as deterministic finite automaton the graph Y plus one additional fail
state. In state P ∈ V (Y ) one can read an element of GP and stay in P or read an
outgoing edge and go to its terminal vertex – all other transitions go to the fail state.
e ∗ where R
e is the set of forbidden factors:
For R, we observe that it is equal to ∆∗ r ∆∗ R∆
e := { gh | ∃P ∈ V (Y ), g, h ∈ GP r {1} } ∪ { yay y | y ∈ E(Y ), a ∈ Gy } .
R

R is thus recognized by a deterministic finite automaton AR that, after reading a word
e (plus a fail state if
u, memorizes in its state the longest suffix of u which is a prefix of R
e
e has linear
it has encountered a full member of R). Since the set of proper prefixes of R
size, AR has a quadratic number of transitions.
Thus, L is a context-free language and we obtain a pushdown automaton for L, which
can be tested for emptiness in polynomial time (for both constructions see e. g. [13]).

20

O(N)

):
Theorem 34. The following problem is in NTIME(22
Input: a context-free grammar G = (V, Σ, P, S) in Chomsky normal form with kGk ≤ N
which generates the word problem of a group G,
Compute a graph of groups with finite vertex groups and fundamental group G.
Note that if G is not in Chomsky normal form, it can be transformed into Chomsky
normal form in quadratic time. In this case the graph of groups can be computed in
O(N 2 )
).
NTIME(22
Theorem 35. The following problem is in NP:
Input: a group G as a virtually free presentation,
Compute a graph of groups with finite vertex groups and fundamental group G.

Table 1: Summary of appearing constants. The third column shows a bound in terms of the
size of a context-free grammar G for the word problem (due to Lemma 8, Lemma 14,
Proposition 12, and Theorem 13), the fourth column shows a bound in terms of the size
of a virtually free presentation V (due to Lemma 28, Lemma 31, Lemma 11, Lemma 29,
and Lemma 31).
N
d
k
K
R=
Ξ
Θ

3kK
2

size of the input
degree of Γ
triangulation constant
maximal weight of a minimal cut
maximal diameter of the boundary of a minimal cut
maximum cardinality of a finite subgroup
maximum number of edges in a reduced graph of groups

kGk
N
2N +2
d3k+3
3k 3k+3
2 d
d12k+10
d12k+11

kVk
N
2N + 2
N2
3(N + 1)N 2
N
N

Proof of Theorem 35 and Theorem 34. We give one proof for both theorems. The difference is only in the form the input is given. Let R, Θ and Ξ are defined as in Lemma 25
and before and let N denote the size of the input (i. e., either N = kVk or N = kGk).
Consider the case of Theorem 34 – i. e., the input is given as context-free grammar
G = (V, Σ, P, S). By Table 1, we have k ∈ O(2N ) where k is the triangulation constant
O(N)
. Now consider the case of Theorem 35 – i. e., the input
of Γ and Ξ, Θ, R ∈ dO(k) ⊆ 22
is given as a virtually free presentation V. By Table 1, Ξ, Θ, R ∈ O(kVkℓ ) for some ℓ ∈ N.
Thus, by Lemma 25 there is a graph of groups G and an isomorphism ϕ : π1 (G, T ) → G
such that
O(N)

(resp. |V (Y )| ∈ O(kVkℓ ))

(i) |V (Y )| ∈ 22

O(N)

for all P ∈ V (Y )
(resp. |GP | ∈ O(kVkℓ ))
S
O(N)
for every a ∈ P ∈V (Y ) GP ∪ E(Y )
(resp. |ϕ(a)| ∈ O(kVkℓ )).
(iii) |ϕ(a)| ∈ 22
S
Let ∆ = P ∈V (Y ) GP ∪ E(Y ) denote the alphabet from Section 2.1. Our algorithm
consists of two steps: first we guess the graph of groups G and a map ϕ : ∆ → G within
the size bounds of Lemma 25 and second we verify that ϕ is indeed an isomorphism
(ii) |GP | ∈ 22

21

Gx

Gx
Gy

Gy

Figure 4: The slide move is possible if there is some g ∈ GP such that g −1 Gxx g ≤ Gyy .
π1 (G, T ) → G using Proposition 33. Lemma 25 assures that there is a valid guess in
the first step and by (i)–(iii) guessing can be done within the time bounds of TheoO(N) )
O(N)
for any polynomial p, so
rem 34 (resp. Theorem 35). Notice that 2p(2
= 22
Proposition 33 yields the desired time bound also in the case of a grammar as input.

6 Slide moves and the isomorphism problem
Given two groups G1 and G2 one can calculate the respective graph of groups and then
check with Krstic’s algorithm by ([15]) whether their fundamental groups are isomorphic.
A closer analysis shows that this algorithm runs in polynomial space. As the description
is quite involved, we follow a different approach based Forester’s theory of deformation
spaces [11, 5].
Let G1 , G2 be the two graph of groups obtained from the presentations of G1 , G2 (with
the vertex groups given as multiplication tables). By construction, we have π1 (G1 , P1 ) ∼
=
G1 and π1 (G2 , P2 ) ∼
= G2 . We will test in PSPACE (more precisely linear space) whether
π1 (G1 , P1 ) ∼
= π1 (G2 , P2 ).
Let G be a graph of groups over Y . A slide move is the following operation on G: let
GP be a vertex group and Gx , Gy edge groups with s(x) = s(y) = P . If Gxx (the image
of Gx in GP ) can be conjugated by an element of GP into Gyy i. e., there is some g ∈ GP
such that g−1 Gxx g ≤ Gyy , then x can be slid along y to Q = t(y), i. e., s(x) is changed
to Q, see Figure 4. The new inclusion of Gx → GQ is then given by ιy ◦ ι−1
y ◦ cg ◦ ιx
where ιx is the inclusion Gx → GP (likewise for ιy , ιy ) and cg is the conjugation with g
(i. e., h 7→ g−1 hg). A slide move induces an isomorphism ϕ of the fundamental groups
of the two graph of groups by ϕ(h) = h for h ∈ GR , R ∈ V (Y ), and ϕ(z) = z for
z ∈ E(Y ) r { x, x } and ϕ(x) = gyx.
Note that slide moves originally were defined on the trees instead of graph of groups.
On trees there is no need for a conjugation before sliding an edge – the conjugation
corresponds simply to choosing a different representative for an edge. In [2] it is shown
that two graph of groups have the same Bass-Serre tree if and only if they are equal up
to conjugation of the inclusions of the edge groups into the vertex groups (this is also
not very hard to see when following the construction of a graph of groups from an action
on a tree in Section 2.1).
The following result is an immediate consequence of [11, Thm. 1.1] and [5, Cor. 3.5]
(resp. [12, Thm. 7.2]). Since we are not aware of an explicit reference, we present the

22

proof.
Proposition 36. Let G1 and G2 be reduced finite graph of groups with finite vertex group.
Then π1 (G1 , P1 ) ∼
= π1 (G2 , P2 ) if and only if G1 can be transformed into G2 by a sequence
of slide moves.
Proof. As described above, slide moves induce isomorphisms on the fundamental groups.
Thus, let G = π1 (G1 , P1 ) ∼
= π1 (G2 , P2 ). This gives us two different actions of G on the
respective Bass-Serre trees. Both actions have the same elliptic subgroups, namely all
finite subgroups. By [11, Thm. 1.1], G1 can be transformed into G2 by a sequence of
elementary deformations. Since the corresponding deformation space is non-ascending
(meaning that there are no self-loops in the graph of groups with one inclusion of the
edge group being surjective but the other not – this clearly cannot happen since all vertex
groups are finite), by [5, Cor. 3.5] or [12, Thm. 7.2], G1 actually can be transformed into
G2 by a sequence of slide moves.
Clearly, any sequence of slide moves can be performed in linear space. By guessing a
sequence of slide moves transforming G1 into G2 , we obtain the following corollary.
Corollary 37. Given two graph of groups G1 and G2 where all vertex groups are given
as full multiplication tables, it can be checked in NSPACE(O(n)) whether π1 (G1 , P1 ) ∼
=
π1 (G2 , P2 ).
In combination with Theorem 34 (and Savitch’s theorem) and Theorem 35 this gives
an algorithm to solve the isomorphism problem for virtually free groups:
O(N)

).
Theorem 38. The isomorphism problem for context-free groups is in DSPACE(22
More precisely, the input is given as two context-free grammars of size at most N which
are guaranteed to generate word problems of groups.
Theorem 39. The isomorphism problem for virtually free groups given as a virtually
free presentation is in PSPACE.

7 Conclusion and open questions
We have shown that the isomorphism problem for virtually free groups is in PSPACE
O(N)
)) depending on the type of input – thus, improving the previous
(resp. DSPACE(22
bound (primitive recursive) significantly. The following questions remain open:
• What is the complexity of the isomorphism problem for virtually free groups given
as an arbitrary presentation?
n

• Is the doubly exponential bound n12·2 +10 on the size of finite subgroups tight or
is there a bound 2p(n) for some polynomial p? This is closely related to another
question:
• What is the minimal size of a context-free grammar of the word problem of a finite
group? Can it be log log(n) where n is the size of the group?

23

• Is there a polynomial bound on the number of slide moves necessary to transform two graphs of groups with isomorphic fundamental groups into each? This
would lead to an NP algorithm for the isomorphism problem with virtually free
presentations as input. We conjecture, however, that this is not true.
Acknowledgements. G.S. thanks the FMI for hosting him from October to the end of
the year 2017. Both authors acknowledge the financial support by the DFG project DI
435/7-1 “Algorithmic problems in group theory” for this work.

References
[1] Yago Antolin. On Cayley graphs of virtually free groups. Groups – Complexity –
Cryptology, 3:301–327, 2011. doi:10.1515/gcc.2011.012.
[2] Hyman Bass. Covering theory for graphs of groups. J. Pure Appl. Algebra, 89(12):3–47, 1993. URL: https://doi.org/10.1016/0022-4049(93)90085-8.
[3] Ron Book and Friedrich Otto. String-Rewriting Systems. Springer-Verlag, 1993.
[4] W. W. Boone. The Word Problem. Ann. of Math., 70(2):207–265, 1959.
[5] Matt Clay and Max Forester. Whitehead moves for G-trees. Bull. Lond. Math.
Soc., 41(2):205–212, 2009. URL: https://doi.org/10.1112/blms/bdn118.
[6] François Dahmani and Vincent Guirardel.
The isomorphism problem for
all hyperbolic groups.
Geom. Funct. Anal., 21(2):223–300, 2011.
URL:
https://doi.org/10.1007/s00039-011-0120-0.
[7] Max Dehn. Ueber unendliche diskontinuierliche Gruppen. Math. Ann., 71:116–144,
1911.
[8] Warren Dicks and Martin J. Dunwoody. Groups acting on graphs. Cambridge
University Press, 1989.
[9] Volker Diekert and Armin Weiß.
Context-Free Groups and Their Structure Trees.
International Journal of Algebra and Computation, 23:611–
642,
2013.
URL: http://dx.doi.org/10.1142/S0218196713500124,
doi:10.1142/S0218196713500124.
[10] Volker Diekert and Armin Weiß. Context-Free Groups and Bass-Serre Theory.
In Juan González-Meneses, Martin Lustig, and Enric Ventura, editors, Algorithmic and Geometric Topics Around Free Groups and Automorphisms, Advanced Courses in Mathematics - CRM Barcelona. Birkhäuser, Basel,
Switzerland, 2017.
URL: http://dx.doi.org/10.1007/978-3-319-60940-9,
doi:10.1007/978-3-319-60940-9.

24

[11] Max Forester. Deformation and rigidity of simplicial group actions on trees. Geom.
Topol., 6:219–267, 2002. URL: https://doi.org/10.2140/gt.2002.6.219.
[12] Vincent Guirardel and Gilbert Levitt. Deformation spaces of trees. Groups Geom.
Dyn., 1(2):135–181, 2007. URL: https://doi.org/10.4171/GGD/8.
[13] John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.
[14] Matthias Jantzen. Confluent String Rewriting, volume 14 of EATCS Monographs
on Theoretical Computer Science. Springer-Verlag, 1988.

[15] Sava Krstic.
Actions of finite groups on graphs and related automorphisms of free groups.
Journal of Algebra, 124:119–138, 1989.
URL:
http://www.sciencedirect.com/science/article/B6WH2-4D7K4TS-PM/2/f3e4483f8194746449447
doi:10.1016/0021-8693(89)90154-3.

[16] P. A. Linnell.
On accessibility of groups.
Journal of
Pure
and
Applied
Algebra,
30(1):39
–
46,
1983.
URL:
http://www.sciencedirect.com/science/article/B6V0K-45FC39Y-3Y/2/ba6029ec8c74928815c3c
doi:DOI:10.1016/0022-4049(83)90037-3.
[17] David E. Muller and Paul E. Schupp. Groups, the theory of ends, and context-free
languages. Journal of Computer and System Sciences, 26:295–310, 1983.
[18] David E. Muller and Paul E. Schupp. The theory of ends, pushdown automata, and
second-order logic. Theoretical Computer Science, 37(1):51–75, 1985.
[19] P. S. Novikov. On the algorithmic unsolvability of the word problem in group theory.
Trudy Mat. Inst. Steklov, pages 1–143, 1955. In Russian.
[20] Christos H. Papadimitriou. Computational Complexity. Addison Wesley, 1994.
[21] Alan
L.
Selman.
A
taxonomy
of
complexity
classes
of
functions.
J.
Comput.
Syst.
Sci.,
48(2):357–381,
1994.
URL:
https://doi.org/10.1016/S0022-0000(05)80009-1,
doi:10.1016/S0022-0000(05)80009-1.
[22] Géraud Sénizergues. An effective version of Stalling’s theorem in the case of contextfree groups. In Andrzej Lingas, Rolf G. Karlsson, and Svante Carlsson, editors, Proc.
20th International Colloquium Automata, Languages and Programming (ICALP
93), Lund (Sweden), volume 700 of Lecture Notes in Computer Science, pages 478–
495. Springer-Verlag, 1993.
[23] Géraud Sénizergues. On the finite subgroups of a context-free group. In Gilbert
Baumslag, David Epstein, Robert Gilman, Hamish Short, and Charles Sims, editors, Geometric and Computational Perspectives on Infinite Groups, number 25 in
DIMACS series in Discrete Mathematics and Theoretical Computer Science, pages
201–212. Amer. Math. Soc., 1996.

25

[24] Jean-Pierre Serre. Trees. Springer, 1980. French original 1977.
[25] Carsten Thomassen and Wolfgang Woess. Vertex-transitive graphs and accessibility.
J. Comb. Theory Ser. B, 58(2):248–268, 1993. doi:10.1006/jctb.1993.1042.

26

