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
|
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. |
Altmetric
Altmetric