Algorithmic aspects of branched coverings II/V. Sphere bisets and their   decompositions
  We consider "Thurston maps": branched self-coverings of the sphere with ultimately periodic critical points, and prove that the Thurston equivalence problem between them (continuous deformation of maps along with their critical orbits) is decidable.   More precisely, we consider the action of mapping class groups, by pre- and post-composition, on branched coverings, and encode them algebraically as "mapping class bisets". We show how the mapping class biset of maps preserving a multicurve decomposes into mapping class bisets of smaller complexity, called "small mapping class bisets".   We phrase the decision problem of Thurston equivalence between branched self-coverings of the sphere in terms of the conjugacy and centralizer problems in a mapping class biset. Our decomposition results on mapping class bisets reduce these decision problems to small mapping class bisets; they correspond to rational maps, homeomorphisms and maps double covered by a torus endomorphism, and their conjugacy and centralizer problems are solvable respectively in terms of complex analysis, group theory and linear algebra.   Branched coverings themselves are also encoded into bisets, with actions of the fundamental groups. We characterize those bisets that arise from branched coverings between topological spheres, and extend this correspondence to maps between spheres with multicurves, whose algebraic counterparts are "sphere trees of bisets".   To illustrate the difference between Thurston maps and homeomorphisms, we produce a Thurston map with infinitely generated centralizer --- while centralizers of homeomorphisms are always finitely generated. 
Laurent Bartholdi and Dzmitry Dudko
math.GR cs.LO math.DS