The Complexity of Temporal Vertex Cover in Small-Degree Graphs

Hamm, Thekla, Klobas, Nina, Mertzios, George B and Spirakis, Paul G ORCID: 0000-0001-5396-3749 (2022) The Complexity of Temporal Vertex Cover in Small-Degree Graphs. In: 36th AAAI Conference on Artificial Intelligence, 2022-2-22 - 2022-3-1, Vancouver , Canada.

Text
Conf_Temporal-Vertex-Cover-Small-Degree-Graphs.pdf - Author Accepted Manuscript
Download (642kB) | Preview

Official URL: http://dx.doi.org/10.1609/aaai.v36i9.21259

Abstract

<jats:p>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 Delta-TVC for time-windows of a fixed-length Delta) 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 Delta-TVC on sparse graphs. Our main result shows that for every Delta geq 2, Delta-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 Delta-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.</jats:p>

Item Type:	Conference or Workshop Item (Unspecified)
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	13 Dec 2021 07:57
Last Modified:	17 Mar 2024 21:00
DOI:	10.1609/aaai.v36i9.21259
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3145253