2015/02/16 by Eleni C. Akrida, Leszek Gąsieniec, Akrida, Eleni C. +5 · 3 citations
Computer Science · #Caching and Content Delivery #Discrete Mathematics (cs.DM) #Distributed systems and fault tolerance #FOS: Computer and information sciences #G.2.2 #Opportunistic and Delay-Tolerant Networks
paper · pdf · doi:10.48550/arxiv.1502.04579
openalex publication_date 2015/02/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the design of small cost temporally connected graphs, under various constraints. We mainly consider undirected graphs of n vertices, where each edge has an associated set of discrete availability instances (labels). A journey from vertex u to vertex v is a path from u to v where successive path edges have strictly increasing labels. A graph is temporally connected iff there is a (u,v)-journey for any pair of vertices u,v,~u\not= 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 can freely choose availability instances for all edges and aims for temporal connectivity with very small cost; 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 in n. 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 instead given a 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 unless P=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, be minimal, i.e., no redundant labels exist. We show the existence of minimal temporal designs with at least n logn labels.