Sharp Thresholds in Random Simple Temporal Graphs



Casteigts, Arnaud, Raskin, Michael, Renken, Malte and Zamaraev, Viktor ORCID: 0000-0001-5755-4141
(2022) Sharp Thresholds in Random Simple Temporal Graphs. In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), 2022-2-7 - 2022-2-10.

[img] Text
2011.03738v1.pdf - Submitted version

Download (327kB) | Preview

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{o}s-R\'enyi random graph $G~G_{n,p}$ by considering a random permutation $\pi$ of the edges and interpreting the ranks in $\pi$ as presence times. 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 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 significant because temporal graphs do not admit spanners of size $O(n)$ in general (Kempe et al, STOC 2000). In fact, they do not even admit spanners of size $o(n^2)$ (Axiotis et al, ICALP 2016). Thus, our result implies that the obstructions found in these works, and more generally, all non-negligible obstructions, must be statistically insignificant: nearly optimal spanners always exist in random temporal graphs. All the above thresholds are sharp. Carrying the study of temporal spanners further, we show that pivotal spanners -- i.e., spanners of size $2n-2$ made 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$.

Item Type: Conference or Workshop Item (Unspecified)
Additional Information: accepted by the SIAM Journal on Computing
Uncontrolled Keywords: Temporal graphs, Random graphs, Connectivity thresholds, Temporal Reachability, Spanners
Depositing User: Symplectic Admin
Date Deposited: 17 Nov 2020 11:40
Last Modified: 26 Dec 2023 07:26
DOI: 10.1109/FOCS52979.2021.00040
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3107243