The Complexity of Temporal Vertex Cover in Small-Degree Graphs

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 $Δ$-TVC for time-windows of a fixed-length $Δ$) 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 $Δ$-TVC on sparse graphs. Our main result shows that for every $Δ\geq 2$, $Δ$-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 $Δ$-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.