Publication details for Dr George MertziosAkrida, E.C., Mertzios, G.B., Spirakis, P.G. & Zamaraev, V. (2020). Temporal vertex cover with a sliding time window. Journal of Computer and System Sciences 107: 108-123.
- Publication type: Journal Article
- ISSN/ISBN: 0022-0000
- DOI: 10.1016/j.jcss.2019.08.002
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
- View in another repository - may include full text
Author(s) from Durham
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.