  We consider the Dynamic Map Visitation Problem (DMVP), in which a team of
agents must visit a collection of critical locations as quickly as possible, in
an environment that may change rapidly and unpredictably during the agents'
navigation. We apply recent formulations of time-varying graphs (TVGs) to DMVP,
shedding new light on the computational hierarchy $\mathcal{R} \supset
\mathcal{B} \supset \mathcal{P}$ of TVG classes by analyzing them in the
context of graph navigation. We provide hardness results for all three classes,
and for several restricted topologies, we show a separation between the classes
by showing severe inapproximability in $\mathcal{R}$, limited approximability
in $\mathcal{B}$, and tractability in $\mathcal{P}$. We also give topologies in
which DMVP in $\mathcal{R}$ is fixed parameter tractable, which may serve as a
first step toward fully characterizing the features that make DMVP difficult.
