Abstract We show that the word problem for any 3-manifold group is solvable in time O (n ^3 n). Our main contribution is the proof that the word problem for admissible graphs of groups, in the sense of Croke and Kleiner, is solvable in O (n n) ; this covers fundamental groups of non-geometric graph manifolds. Similar methods also give that the word problem for free products can be solved “almost as quickly” as the word problem in the factors.
Sisto et al. (Mon,) studied this question.