Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

The complexity of temporal vertex cover in small-degree graphs

Hamm, T. and Klobas, N. and Mertzios, G.B. and Spirakis, P.G. (2022) 'The complexity of temporal vertex cover in small-degree graphs.', 36th AAAI Conference on Artificial Intelligence (AAAI) Vancouver, BC, Feb 22 - Mar 01 2022.

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.

Item Type:Conference item (Paper)
Full text:Publisher-imposed embargo
(AM) Accepted Manuscript
File format - PDF
(628Kb)
Status:Peer-reviewed
Publisher Web site:https://aaai.org/Conferences/AAAI-22/
Date accepted:02 December 2021
Date deposited:09 December 2021
Date of first online publication:2022
Date first made open access:No date available

Save or Share this output

Export:
Export
Look up in GoogleScholar