Temporal vertex cover with a sliding time window

Akrida, E.C.; Mertzios, G.B.; Spirakis, P.G.; Zamaraev, V.

Abstract

Modern, inherently dynamic systems are usually characterized by a network structure which is subject to discrete changes over time. Given a static underlying graph, a temporal graph can be represented via an assignment of a set of integer time-labels to every edge, indicating the discrete time steps when this edge is active. While most of the recent theoretical research on temporal graphs focused on temporal paths and other “path-related” temporal notions, only few attempts have been made to investigate “non-path” temporal problems. In this paper we introduce and study two natural temporal extensions of the classical problem VERTEX COVER. We present a thorough investigation of the computational complexity and approximability of these two temporal covering problems. We provide strong hardness results, complemented by 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.

Citation

Akrida, E., Mertzios, G., Spirakis, P., & Zamaraev, V. (2020). Temporal vertex cover with a sliding time window. Journal of Computer and System Sciences, 107, 108-123. https://doi.org/10.1016/j.jcss.2019.08.002

• Journal Article Type: Article
• Acceptance Date: Aug 9, 2019
• Online Publication Date: Aug 21, 2019
• Publication Date: Feb 28, 2020
• Deposit Date: Aug 11, 2019
• Publicly Available Date: Aug 21, 2020
• Journal: Journal of Computer and System Sciences
• Print ISSN: 0022-0000
• Electronic ISSN: 1090-2724
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 107
• Pages: 108-123
• DOI: https://doi.org/10.1016/j.jcss.2019.08.002
• Public URL: https://durham-repository.worktribe.com/output/1290601
• Related Public URLs: https://arxiv.org/abs/1802.07103