  Temporal graphs naturally model graphs whose underlying topology changes over
time. Recently, the problems TEMPORAL VERTEX COVER (or TVC) and SLIDING-WINDOW
TEMPORAL VERTEX COVER(or $\Delta$-TVC for time-windows of a fixed-length
$\Delta$) have been established as natural extensions of the classic problem
VERTEX COVER on static graphs with connections to areas such as surveillance in
sensor networks. In this paper we initiate a systematic study of the complexity
of TVC and $\Delta$-TVC on sparse graphs. Our main result shows that for every
$\Delta\geq 2$, $\Delta$-TVC is NP-hard even when the underlying topology is
described by a path or a cycle. This resolves an open problem from literature
and shows a surprising contrast between $\Delta$-TVC and TVC for which we
provide a polynomial-time algorithm in the same setting. To circumvent this
hardness, we present a number of exact and approximation algorithms for
temporal graphs whose underlying topologies are given by a path, that have
bounded vertex degree in every time step, or that admit a small-sized temporal
vertex cover.
