The complexity of temporal vertex cover in small-degree graphs

Hamm, T.; Klobas, N.; Mertzios, G.B.; Spirakis, P.G.

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.

Citation

Hamm, T., Klobas, N., Mertzios, G., & Spirakis, P. (2023, February). The complexity of temporal vertex cover in small-degree graphs. Presented at 36th AAAI Conference on Artificial Intelligence (AAAI 2022), Vancouver, BC

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 36th AAAI Conference on Artificial Intelligence (AAAI 2022)
• Start Date: Feb 22, 2023
• End Date: Mar 1, 2022
• Acceptance Date: Dec 2, 2021
• Publication Date: Jun 28, 2022
• Deposit Date: Dec 8, 2021
• Publisher: Association for the Advancement of Artificial Intelligence
• Pages: 10193-10201
• Series Number: 9
• DOI: https://doi.org/10.1609/aaai.v36i9.21259
• Keywords: Search And Optimization (SO), Planning, Routing, And Scheduling (PRS)
• Public URL: https://durham-repository.worktribe.com/output/1138041