Temporal Vertex Cover with a Sliding Time Window


Akrida, Eleni C ORCID: 0000-0002-1126-1623, Mertzios, George B, Spirakis, Paul G ORCID: 0000-0001-5396-3749 and Zamaraev, Viktor ORCID: 0000-0001-5755-4141 (2018) Temporal Vertex Cover with a Sliding Time Window. In: International; Colloquium on Automata , Languages and Programming (ICALP), 2018-7-9 - 2018-7-13, Prague.

This is the latest version of this item.

Access the full-text of this item by clicking on the Open Access link.
[img] Text
1802.07103v1.pdf - Submitted version
Available under License : See the attached licence file.
Download (623kB)
[img] Text
Delta_TVC-_Arxiv_180218.pdf - Author Accepted Manuscript
Available under License : See the attached licence file.
Download (595kB)
[img] Text
1802.07103v1.pdf - Submitted version
Available under License : See the attached licence file.
Download (623kB)

Abstract

Modern, inherently dynamic systems are usually characterized by a network structure, i.e. an underlying graph topology, which is subject to discrete changes over time. Given a static underlying graph $G$, a temporal graph can be represented via an assignment of a set of integer time-labels to every edge of $G$, indicating the discrete time steps when this edge is active. While most of the recent theoretical research on temporal graphs has focused on the notion of a temporal path and other "path-related" temporal notions, only few attempts have been made to investigate "non-path" temporal graph problems. In this paper, motivated by applications in sensor and in transportation networks, we introduce and study two natural temporal extensions of the classical problem Vertex Cover. In both cases we wish to minimize the total number of "vertex appearances" that are needed to "cover" the whole temporal graph. In our first problem, Temporal Vertex Cover, the aim is to cover every edge at least once during the lifetime of the temporal graph, where an edge can be covered by one of its endpoints, only at a time step when it is active. In our second, more pragmatic variation Sliding Window Temporal Vertex Cover, we are also given a natural number $\Delta$, and our aim is to cover every edge at least once at every $\Delta$ consecutive time steps. We present a thorough investigation of the computational complexity and approximability of these two temporal covering problems. In particular, we provide strong hardness results, complemented by various approximation and exact algorithms. Some of our algorithms are polynomial-time, while others are asymptotically almost optimal under the Exponential Time Hypothesis (ETH) and other plausible complexity assumptions.

Item Type: Conference or Workshop Item (Unspecified)
Uncontrolled Keywords: cs.CC, cs.CC
Depositing User: Symplectic Admin
Date Deposited: 17 Dec 2020 10:12
Last Modified: 18 Jan 2023 23:18
DOI: 10.4230/LIPIcs.ICALP.2018.148
Open Access URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2018.148
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3110032

Available Versions of this Item

Dimensions
Altmetric
CORE (COnnecting REpositories)