The complexity of temporal vertex cover in small-degree graphs

Abstract

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 Vertex Cover problem 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 ∆ ≥ 2, ∆-TVC is NPhard 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 polynomialtime 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 smallsized temporal vertex cover.