Temporal vertex cover with a sliding time window
Temporal vertex cover with a sliding time window
复制标题
具有滑动时间窗口的时间顶点覆盖
DOI：
10.1016/j.jcss.2019.08.002
复制
发表时间：
2020
影响因子：
1.1
通讯作者：
Akrida E
中科院分区：
文献类型：
--
作者：
Akrida E
现代的内在动态系统通常以网络结构为特征，即底层图形拓扑，其随时间发生离散变化。给定一个静态的底层图，一个时间图可以通过一组整数时间标签分配给每个边来表示，指示该边活动时的离散时间步长。虽然大多数最近的理论研究时间图的时间路径和其他“路径相关”的时间概念的概念集中，只有少数尝试已经调查“非路径”时间图的问题。在本文中，在传感器和运输网络中的应用的动机，我们介绍和研究两个自然的时间扩展的经典问题顶点覆盖。在这两种情况下，我们都希望最小化“覆盖”整个时间图所需的“顶点出现”的总数。在我们的第一个问题Temporal Vertex Cover中，目标是在时间图的生命周期内至少覆盖每一条边一次，其中一条边可以被其端点之一覆盖，只有在它处于活动状态的时间步。在我们的第二个，更务实的变化滑动窗口时间顶点覆盖，我们也给出了一个自然数，我们的目标是覆盖每个边缘至少一次在每个连续的时间步骤。我们提出了一个彻底的调查这两个时间覆盖问题的计算复杂性和可逼近性。特别是，我们提供了强大的硬度结果，辅以各种近似和精确算法。我们的一些算法是多项式时间的，而另一些算法在指数时间假设（ETH）和其他合理的复杂性假设下是渐近几乎最优的。
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, a temporal graph can be represented via an assignment of a set of integer time-labels to every edge of, 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, and our aim is to cover every edge at least once at everyconsecutive 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.