  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$.
