论文标题
颞顶点盖的复杂性在小图中
The Complexity of Temporal Vertex Cover in Small-Degree Graphs
论文作者
论文摘要
时间图自然建模，其潜在拓扑随时间变化的图形变化。最近，已确定了暂时顶点盖（或TVC）和滑动窗口的暂时顶点盖（或固定长度$δ$的时间窗口的$δ$ -TVC），作为经典问题顶点的自然延伸，在静态图形上具有与传感器网络中监视等区域的静态图形上的自然延伸。在本文中，我们对稀疏图上TVC和$δ$ -TVC的复杂性进行系统研究。我们的主要结果表明，即使在路径或周期描述了基础拓扑时，每个$δ\ geq 2 $，$δ$ -TVC也是NP-HARD。这解决了文献中的一个空旷问题，并在$δ$ -TVC和TVC之间形成了令人惊讶的对比，我们在同一环境中为此提供了多项式时间算法。为了避免这种硬度，我们为时间表提供了许多精确和近似算法，其基本拓扑由路径给出，在每个时间步骤中都具有界限顶点度，或者允许小型的时间顶点盖。
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 $Δ$-TVC for time-windows of a fixed-length $Δ$) have been established as natural extensions of the classic problem VERTEX COVER 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 $Δ$-TVC on sparse graphs. Our main result shows that for every $Δ\geq 2$, $Δ$-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 $Δ$-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.
