The Dynamic Map Visitation Problem: Foremost Waypoint Coverage of Time-Varying Graphs

This thesis introduces 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.