Given a map $\psi: S\rightarrow S,$ for $S$ a closed surface, is there any algorithm to compute its translation distance in the curve complex? I should say that I mostly care about checking that the translation distance is/is not very small. That is, if the algorithm can pick among the possibilities: translation distance is 0, 1, 2, 3, many, then I am happy...
I know there are algorithms for computing distances IN the curve complex, but this is not quite the same...
In the case that $\psi$ is pseudo-Anosov, the best one can do in general, as far as I know, is to get upper and lower bounds which are linear in translation length. These come from train track considerations. Assuming you have an invariant train track $T$ for $\psi$ in your hands (obtained by some algorithmic method of currently unknowable complexity as per my comment), factor it into a sequence of train track splits $$T=T_0, T_1, \ldots, T_k = \psi(T) $$ then using the method in the Masur-Minsky paper "Geometry of the curve comples I: hyperbolicity", one can algorithmically break the split sequence into blocks $$T_0 = T_{m_0}, ..., T_{m_1}, ..., T_{m_a}=T_k $$ such that the diameter of the subsequence from $T_{m_i}$ to $T_{m_{i+1}}$ has a certain constant upper bound and the diameter from $T_{m_i}$ to $T_{m_j}$ has a certain lower bound which is a constant times $|i-j|$. The material needed to do this is described in the section of their paper entitled "the nested train track argument".
Other than that, Shackleton's paper "An acylindricity theorem for the mapping class group" contains some algorithmic detail, but not enough to answer your question.
Recently, Richard Webb and myself gave a polynomial-time algorithm for computing the asymptotic translation length of a mapping class $$ \ell(h) = \lim_{n \to \infty} d(x, h^n(x)). $$ This appears as Algorithm 6 of the paper and relies on being able to compute geodesics in the curve complex. Assuming this, the key observation is that a midpoint $c'$ of a curve $c$ and its image under a large enough power of $h$ lies close to the tight axis of $h$. Hence $d(c', h^n(c')) \approx n \ell(h)$. Therefore, since $\ell(h)$ is a rational number with bounded denominator, if we take $n$ large enough then $$ \ell(h) = \frac{1}{n} d(c', h^n(c')). $$
If you fix a finite generating set $\langle X \rangle = \textrm{Mod}(S)$ then the running time of this algorithm is a polynomial function of the word length of the mapping class $|h|_X$ since this is the running time of our algorithm for computing a geodesic from $c$ to $h(c)$ (Algorithm 4).
I don't know an algorithm, but here's a possible approach. As Richard and Lee have observed, one may assume that $\psi$ is pseudo-Anosov. In that case, the mapping torus $T_\psi$ is a hyperbolic 3-manifold fibering over $S^1$, with fiber $S$. There is a short exact sequence $\pi_1(S)\to\pi_1(T_\psi)\to \mathbb{Z}$.
Here's a characterization of the translation length on the curve complex in terms of the topology of $T_\psi$. The fiber $S$ represents a homology class $[S]\in H_2(T_\psi)$. Let $\Sigma \looparrowright T_\psi$ be an immersed connected surface, such that $[\Sigma]=k[S]$ and such that $\chi(\Sigma)=k\chi(S)$. Moreover, assume that the composite map $\pi_1(\Sigma)\to \pi_1(T_\psi) \to \mathbb{Z}$ is non-trivial, so that $\Sigma$ is not homotopic to a finite-sheeted cover of $S$. Let $K(\psi)$ be the minimal such $k$, and let $D(\psi)$ be the minimal such $k$ so that the surface has only double curves of intersection. Clearly $K(\psi)\leq D(\psi)$.
Claim: The curve complex translation distance of $\psi$ is $=D(\psi)$.
One direction: Let $k$ be the translation length of $\psi$. There exists a sequence of non-separating curves $c_1,c_2,\ldots, c_k \subset S$, such that $\psi(c_1)=c_k$, and $c_i \cap c_{i+1}=\emptyset$. One creates a surface $\Sigma\subset T_\psi$ by taking $k$ copies of $S$, $S_1 \sqcup \cdots \sqcup S_k \subset T_\psi$ in circular order. Cut out annular neighborhoods of $c_i, c_{i+1}$ inside $S_i$, and insert cross annuli between $S_{i-1}$ and $S_i$ (taking indices $\mod k$) between the 4 copies of $c_i$. This construction generalizes a construction of Cooper-Long-Reid. One can see that the resulting surface has the properties above.
Conversely, if one has such an immersed surface with only double curves, one may cut and paste the self-intersection curves to get $k$ parallel copies of $S$. The cross cut curves gives a sequence of closed curves in $S$, which one can prove using the homology condition forms a closed loop in the curve complex $\mod \psi$.
I don't know yet how to make this criterion into an algorithm. I think there is an algorithm to compute $K(\psi)$. For a given genus $g$, Canary proved that there are only finitely many homotopy classes of immersed surfaces of genus $g$. I think this proof can be made effective, and should give one a method to compute $K(\psi)$. This would at least give an algorithmic lower bound, since $K(\psi)\leq D(\psi)$. Also, there is a constant $0< c_S <1$ such that $D(\psi)\leq c_S K(\psi)$ (this may be proved using hyperbolic geometry techniques).
One could try to algorithmically to construct all surfaces realizing $K(\psi)$, and then try to homotope them to have only double curves of intersection, e.g. using normal surfaces. However, there is a result of Gulliver-Scott that an immersed surface with only double curves of intersection might have a minimal area representative which has triple points. So I don't know yet how to make an algorithm by computing $D(\psi)$ using this approach.
In the braid group, Ko and Lee have given a polynomial time test of reducibility using the Garside structure. (See http://arxiv.org/abs/math/0610746)
