Partial temporal vertex cover with bounded activity intervals

• In this paper we study a variant of Vertex Cover where the activities of vertices are characterized by time intervals. We explore a scenario where the temporal span of each vertex’s activity interval is bounded by an integer, and the objective is to maximize the number of (temporal) edges that are covered. • We establish the APX-hardness of this problem and the NP-hardness of the corresponding decision problem, even under the restricted conditions where: the temporal domain comprises only two timestamps and each edge appears at most once and; no two edges are associated to a same label. • We delve into the parameterized complexity of the problem, offering two fixed-parameter algorithms parameterized by: the number k of temporal edges covered by the solution, and the number h of temporal edges left uncovered by the solution. • We focus again on the approximability of the problem and present a polynomial-time approximation algorithm achieving a factor of 3 4 . Different variants of Vertex Cover have recently garnered attention in the context of temporal graphs. One of these variants is motivated by the need to summarize timeline activities in social networks. Here, the activities of individual vertices, representing users, are characterized by time intervals. In this paper, we explore a scenario where the temporal span of each vertex’s activity interval is bounded by an integer ℓ, and the objective is to maximize the number of (temporal) edges that are covered. We establish the APX-hardness of this problem and the NP-hardness of the corresponding decision problem, even under the restricted conditions where: the temporal domain comprises only two timestamps and each edge appears at most once and; no two edges are associated to a same label. Subsequently, we delve into the parameterized complexity of the problem, offering two fixed-parameter algorithms parameterized by: (i) the number k of temporal edges covered by the solution, and (ii) the number h of temporal edges not covered by the solution. Finally, we present a polynomial-time approximation algorithm achieving a factor of 3 4 .