论文标题
计算时间连接的最佳标签的复杂性
The complexity of computing optimum labelings for temporal connectivity
论文作者
论文摘要
如果存在严格的时间路径，则在时间上连接图，即，从每个顶点$ u $到其他每个顶点$ v $，其边缘严格增加标签的路径。在本文中，我们研究了无方向连接图的时间设计问题。这些优化问题的基本设置如下：给定连接的无向图$ g $，我们需要添加到$ g $的边缘的最小数字$ |λ| $是什么是$ g $的边缘，使得结果的暂时图$（g，λ）$是暂时连接的？事实证明，这个称为最小标签（ML）的基本问题可以在多项式时间内最佳地解决。但是，利用时间维度，问题在以下变化中变得更加有趣和有意义，我们在本文中进行了研究。首先，我们考虑问题最小。当我们在所获得的时间图$（g，λ）$的允许年龄（即最大标签）上给我们时，将图表的老化标记（mal）在时间上连接图。其次，我们考虑问题最小。 Steiner标记（MSL），目前的目标是在任何一对“终端”顶点之间具有时间路径，该顶点位于子集$ r \ subseteq v $中。这个轻松的问题类似于静态图中的斯坦纳树。但是，由于要求在时间路径中严格增加标签，因此Steiner树不是MSL的特殊情况。最后，我们考虑了MSL年龄限制的版本，即最低版本。老化的Steiner标签（MASL）。我们的主要结果是三倍：我们证明（i）mal在无向图上变为np complete，而（ii）MASL相对于终端的数量$ | r | $。另一方面，我们证明（iii）尽管年龄无限制的问题MSL是NP-HARD，但在终端的数量$ | r | $方面是fpt。也就是说，补充年龄限制，使上述问题严格困难。
A graph is temporally connected if there exists a strict temporal path, i.e. a path whose edges have strictly increasing labels, from every vertex $u$ to every other vertex $v$. In this paper we study temporal design problems for undirected temporally connected graphs. The basic setting of these optimization problems is as follows: given a connected undirected graph $G$, what is the smallest number $|λ|$ of time-labels that we need to add to the edges of $G$ such that the resulting temporal graph $(G,λ)$ is temporally connected? As it turns out, this basic problem, called MINIMUM LABELING (ML), can be optimally solved in polynomial time. However, exploiting the temporal dimension, the problem becomes more interesting and meaningful in its following variations, which we investigate in this paper. First we consider the problem MIN. AGED LABELING (MAL) of temporally connecting the graph when we are given an upper-bound on the allowed age (i.e. maximum label) of the obtained temporal graph $(G,λ)$. Second we consider the problem MIN. STEINER LABELING (MSL), where the aim is now to have a temporal path between any pair of "terminals" vertices which lie in a subset $R\subseteq V$. This relaxed problem resembles STEINER TREE in static graphs. However, due to the requirement of strictly increasing labels in a temporal path, STEINER TREE is not a special case of MSL. Finally we consider the age-restricted version of MSL, namely MIN. AGED STEINER LABELING (MASL). Our main results are threefold: we prove that (i) MAL becomes NP-complete on undirected graphs, while (ii) MASL becomes W[1]-hard with respect to the number $|R|$ of terminals. On the other hand we prove that (iii) although the age-unrestricted problem MSL is NP-hard, it is in FPT with respect to the number $|R|$ of terminals. That is, adding the age restriction, makes the above problems strictly harder.
