  The ARRIVAL problem is to decide the fate of a train moving along the edges
of a directed graph, according to a simple (deterministic) pseudorandom walk.
The problem is in $NP \cap coNP$ but not known to be in $P$. The currently best
algorithms have runtime $2^{\Theta(n)}$ where $n$ is the number of vertices.
This is not much better than just performing the pseudorandom walk. We develop
a subexponential algorithm with runtime $2^{O(\sqrt{n}\log n)}$. We also give a
polynomial-time algorithm if the graph is almost acyclic. Both results are
derived from a new general approach to solve ARRIVAL instances.
