  Let $G$ be a directed graph with $n$ vertices and $m$ edges, embedded on a
surface $S$, possibly with boundary, with first Betti number $\beta$. We
consider the complexity of finding closed directed walks in $G$ that are either
contractible (trivial in homotopy) or bounding (trivial in integer homology) in
$S$. Specifically, we describe algorithms to determine whether $G$ contains a
simple contractible cycle in $O(n+m)$ time, or a contractible closed walk in
$O(n+m)$ time, or a bounding closed walk in $O(\beta (n+m))$ time. Our
algorithms rely on subtle relationships between strong connectivity in $G$ and
in the dual graph $G^*$; our contractible-closed-walk algorithm also relies on
a seminal topological result of Hass and Scott. We also prove that detecting
simple bounding cycles is NP-hard.
  We also describe three polynomial-time algorithms to compute shortest
contractible closed walks, depending on whether the fundamental group of the
surface is free, abelian, or hyperbolic. A key step in our algorithm for
hyperbolic surfaces is the construction of a context-free grammar with
$O(g^2L^2)$ non-terminals that generates all contractible closed walks of
length at most L, and only contractible closed walks, in a system of quads of
genus $g\ge2$. Finally, we show that computing shortest simple contractible
cycles, shortest simple bounding cycles, and shortest bounding closed walks are
all NP-hard.
