The Complexity of Optimal Design of Temporally Connected Graphs



Akrida, Eleni C, Gasieniec, Leszek ORCID: 0000-0003-1809-9814, Mertzios, George B and Spirakis, Paul G ORCID: 0000-0001-5396-3749
(2017) The Complexity of Optimal Design of Temporally Connected Graphs THEORY OF COMPUTING SYSTEMS, 61 (3). pp. 907-944. ISSN 1432-4350, 1433-0490

[thumbnail of paper.pdf] Text
paper.pdf - Author Accepted Manuscript

Download (818kB)

Abstract

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 ≠ 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 nlogn labels.

Item Type: Article
Uncontrolled Keywords: Temporal graphs, Network design, Temporally connected, Minimal graph, APX-hard, Random input
Depositing User: Symplectic Admin
Date Deposited: 28 Feb 2017 09:36
Last Modified: 24 Jun 2026 19:59
DOI: 10.1007/s00224-017-9757-x
Related Websites:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3006091
Disclaimer: The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.