The Complexity of Optimal Design of Temporally Connected Graphs.
The Complexity of Optimal Design of Temporally Connected Graphs.
复制标题
时间连通图优化设计的复杂性。
DOI：
10.1007/s00224-017-9757-x
复制
发表时间：
2017
影响因子：
0.5
通讯作者：
Akrida EC
中科院分区：
文献类型：
--
作者：
Akrida EC
我们研究了在各种约束条件下，小成本时间连通图的设计。我们主要考虑无向图ofnvertices，其中每个边有一个相关的离散的可用性实例（标签）的集合。从顶点到顶点的旅程是从顶点到顶点的路径，其中连续的路径边具有严格递增的标签。一个图是时间连通的当且仅当对于任意一对顶点u，v，u ∈ v存在（u，v）-行程.我们首先给出一个简单的多项式时间算法来检查给定的时间图是否是时间连接的。然后，我们考虑的情况下，时间图的设计者canfreely promisesavailability实例的所有边缘，并以非常小的成本的时间连接的目标，成本是可用性实例的总数使用。我们通过一个简单的多项式时间程序，推导出成本线性inn的设计。我们还表明，上述过程是（几乎）最优的基础图是一棵树，通过证明任何树的成本的下界。然而，也有实用的情况下，一个是不能自由地重新设计一个时间连接的图，但insteadgivena时间图设计与索赔，它是时间连接的，并希望通过删除标签，而不破坏时间连接（冗余标签），使其更具成本效益。我们的主要技术结果是，计算冗余标签的最大数量是APX困难的，即，没有PTAS除非P =NP。在积极的一面，我们表明，在稠密的随机边缘可用性图，有渐近几乎肯定是一个非常大的冗余标签。然而，临时设计可以是临时的，即，不存在冗余标签。我们证明了至少有nlognlabels的极小时态设计的存在性。
We study the design of small cost temporally connected graphs, under various constraints. We mainly consider undirected graphs ofnvertices, where each edge has an associated set of discrete availability instances (labels). A journey from vertexuto vertexvis a path fromutovwhere successive path edges have strictly increasing labels. A graph is temporally connected iff there is a (u,v)-journey for any pair of verticesu,v,u≠v. We first give a simple polynomial-time algorithm to check whether a given temporal graph is temporally connected. We then consider the case in which a designer of temporal graphs canfreely chooseavailability instances for all edges and aims for temporal connectivity with very smallcost; the cost is the total number of availability instances used. We achieve this via a simple polynomial-time procedure which derives designs of cost linear inn. We also show that the above procedure is (almost) optimal when the underlying graph is a tree, by proving a lower bound on the cost for any tree. However, there are pragmatic cases where one is not free to design a temporally connected graph anew, but is insteadgivena temporal graph design with the claim that it is temporally connected, and wishes to make it more cost-efficient by removing labels without destroying temporal connectivity (redundant labels). Our main technical result is that computing the maximum number of redundant labels is APX-hard, i.e., there is no PTAS unlessP=NP. On the positive side, we show that in dense graphs with random edge availabilities, there is asymptotically almost surely a very large number of redundant labels. A temporal design may, however, beminimal, i.e., no redundant labels exist. We show the existence of minimal temporal designs with at leastnlognlabels.