  In \cite{Ka14} we produced an algorithm for deciding whether or not an
element $\phi\in Out(F_N)$ is an iwip ("fully irreducible") automorphism. At
several points that algorithm was rather inefficient as it involved some
general enumeration procedures as well as running several abstract processes in
parallel. In this paper we refine the algorithm from \cite{Ka14} by eliminating
these inefficient features, and also by eliminating any use of mapping class
groups algorithms.
  Our main result is to produce, for any fixed $N\ge 3$, an algorithm which,
given a topological representative $f$ of an element $\phi$ of $Out(F_N)$,
decides in polynomial time in terms of the "size" of $f$, whether or not $\phi$
is fully irreducible.
  In addition, we provide a train track criterion of being fully irreducible
which covers all fully irreducible elements of $Out(F_N)$, including both
atoroidal and non-atoroidal ones.
  We also give an algorithm, alternative to that of Turner, for finding all the
indivisible Nielsen paths in an expanding train track map, and estimate the
complexity of this algorithm.
  An appendix by Mark Bell provides a polynomial upper bound, in terms of the
size of the topological representative, on the complexity of the
Bestvina-Handel algorithm \cite{BH92} for finding either an irreducible train
track representative or a topological reduction.

Group Theory;Geometric Topology