Uniformly polynomial-time classification of surface homeomorphisms

Abstract We describe an algorithm which, given two essential curves on a surface S , computes their distance in the curve graph of S , up to multiplicative and additive errors. As an application, we present an algorithm to decide the Nielsen–Thurston type (periodic, reducible, or pseudo-Anosov) of a mapping class of S . The novelty of our algorithms lies in the fact that their running time is polynomial in the size of the input and in the complexity of S —say, its Euler characteristic. This is in contrast with previously known algorithms, which run in polynomial time in the size of the input for any fixed surface S .