Casteigts, Arnaud, Raskin, Michael, Renken, Malte and Zamaraev, Viktor
(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.
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: | 09 Sep 2024 04:26 |
DOI: | 10.1109/FOCS52979.2021.00040 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3107243 |