Sharp Thresholds in Random Simple Temporal Graphs

Casteigts, Arnaud ORCID: 0000-0002-7819-7013, Raskin, Michael ORCID: 0000-0002-6660-5673, Renken, Malte ORCID: 0000-0002-1450-1901 and Zamaraev, Viktor ORCID: 0000-0001-5755-4141 (2024) Sharp Thresholds in Random Simple Temporal Graphs. SIAM Journal on Computing, 53 (2). pp. 346-388.

Text 2011.03738v4.pdf - Author Accepted Manuscript Access to this file is restricted: awaiting official publication and publisher embargo. Download (742kB)

Abstract

A graph whose edges only appear at certain points in time is called a temporal graph (among other names). Such a graph is temporally connected if each ordered pair of vertices is connected by a path which traverses edges in chronological order (i.e., a temporal path). In this paper, we consider a simple model of random temporal graph, obtained from an Erd\H os-R\'enyi random graph, G \sim Gn,p, by considering a random permutation \pi of the edges and interpreting the ranks in \pi as presence times. We give a thorough study of the temporal connectivity of such graphs and derive implications for the existence of several kinds of sparse spanners. It turns out that temporal reachability in this model exhibits a surprisingly regular sequence of thresholds. In particular, we show that at p = log n/n, any fixed pair of vertices can asymptotically almost surely (a.a.s.) reach each other; at 2 log n/n, at least one vertex (and, in fact, any fixed vertex) can a.a.s. reach all others; and at 3 log n/n, all the vertices can a.a.s. reach each other; i.e., the graph is temporally connected. Furthermore, the graph admits a temporal spanner of size 2n + o(n) as soon as it becomes temporally connected, which is nearly optimal, as 2n - 4 is a lower bound. This result is quite significant because temporal graphs do not admit spanners of size O(n) in general [Kempe, Kleinberg, and Kumar, J. Comput. System Sci., 64 (2002), pp. 820-842]. In fact, they do not even always admit spanners of size o(n2) [Axiotis and Fotakis, On the size and the approximability of minimum temporally connected subgraphs, 2016, pp. 149:1-149:14]. Thus, our result implies that the obstructions found in these works-and more generally any non-negligible obstruction-are statistically insignificant: nearly optimal spanners always exist in random temporal graphs. All the above thresholds are sharp. Carrying the study of temporal spanners a step further, we show that pivotal spanners-i.e., spanners of size 2n- 2 composed of two spanning trees glued at a single vertex (one descending in time, the other ascending subsequently)-exist a.a.s. at 4 log n/n, this threshold being also sharp. Finally, we show that optimal spanners (of size 2n - 4) also exist a.a.s. at p = 4 log n/n. Whether this value is a sharp threshold is open; we conjecture that it is. For completeness, we compare the above results to existing results in related areas, including edge-ordered graphs, gossip theory, and population protocols, showing that our results can be interpreted in these settings as well and that in some cases they improve known results therein. Finally, we discuss an intriguing connection between our results and Janson's celebrated results on percolation in weighted graphs.

Item Type:	Article
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	09 Jan 2024 11:56
Last Modified:	02 May 2024 17:49
DOI:	10.1137/22m1511916
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3177699