Spanners and connectivity problems in temporal graphs

10^th November 2022, 10:00 Zoom
Prof. Arnaud Casteigts
LaBRI, University of Bordeaux

Abstract

A graph whose edges only appear at certain points in time is called a
temporal graph. These graphs are temporally connected if all the nodes
can reach each other through path that traverses edges in chronological
order (i.e., a temporal path). In this talk, I will present some general
facts about temporal reachability. Then, I will focus on the particular
problem of finding small subgraphs that preserve temporal connectivity
(i.e., a temporal spanner). Quite surprisingly, Axiotis and Fotakis
showed in [1] that small spanners do not always exist in temporal
graphs, in stark contrast with standard graphs. I will then review some
positive results that we obtained recently, including the fact that
spanners of size O(n log n) always exist in temporal cliques [2], and
that quasi-optimal spanners exist with high probability in random
temporal graphs [3].

[1] Axiotis and Fotakis, On the size and the approximability of minimum
temporally connected subgraphs (ICALP 2016)
[2] Casteigts, Peters, Schoeters, Temporal cliques admit sparse spanners
(ICALP 2019)
[3] Casteigts, Raskin, Renken, Zamaraev, Sharp thresholds in random
simple temporal graphs (FOCS 2021)