Sharp Thresholds in Random Simple Temporal Graphs

DOI10.1137/22M1511916arXiv2011.03738OpenAlexW3098783518MaRDI QIDQ6131198FDOQ6131198

Michael Raskin, Malte Renken, Arnaud Casteigts, Victor Zamaraev

Publication date: 4 April 2024

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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 ErdH{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=logn/n$ any fixed pair of vertices can a.a.s. reach each other; at $2logn/n$ at least one vertex (and in fact, any fixed vertex) can a.a.s. reach all others; and at $3logn/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 $4logn/n$, this threshold being also sharp. Finally, we show that optimal spanners (of size $2n-4$) also exist a.a.s. at $p=4logn/n$.

Full work available at URL: https://arxiv.org/abs/2011.03738

zbMATH Keywords

sharp thresholdedge-ordered graphErdős-Renyi random graphtemporal reachabilitygossiping protocolrandom temporal graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorics in computer science (68R05)

Cites Work

• Title not available (Why is that?)
• Random graphs.
• A strong-connectivity algorithm and its applications in data flow analysis
• Weighted sums of certain dependent random variables
• Flooding time in edge-Markovian dynamic graphs
• How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
• Increasing paths in edge ordered graphs
• Increasing Hamiltonian paths in random edge orderings
• One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
• Some Combinatorial Theorems on Monotonicity
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs
• The shortest-path problem for graphs with random arc-lengths
• Connectivity and inference problems for temporal networks
• Title not available (Why is that?)
• Introduction to Random Graphs
• Computation in networks of passively mobile finite-state sensors
• Assigning times to minimise reachability in temporal graphs
• Broadcasting in dynamic radio networks
• Temporal Network Theory
• Parsimonious flooding in dynamic graphs
• Evolving graphs: dynamical models, inverse problems and propagation
• A Problem with Telephones
• Computing maximum matchings in temporal graphs.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Temporal graph classes: a view through temporal separators
• Reachability and expectation in gossiping
• The complexity of optimal design of temporally connected graphs
• Finding temporal paths under waiting time constraints
• Temporal cliques admit sparse spanners
• How fast can we reach a target vertex in stochastic temporal graphs?
• On the Size and the Approximability of Minimum Temporally Connected Subgraphs
• Temporal vertex cover with a sliding time window
• Sliding window temporal graph coloring
• Nearly-linear monotone paths in edge-ordered graphs
• Probabilistic Analysis of Rumor-Spreading Time
• Long Monotone Trails in Random Edge-Labellings of Random Graphs
• Most edge‐orderings of K_n have maximal altitude
• Random exchanges of information
• Random exchanges of information

This page was built for publication: Sharp Thresholds in Random Simple Temporal Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6131198)