Lecture by Arnaud Casteigts (Université de Bordeaux): Spanners and connectivity problems in temporal graphs
A graph whose edges only appear at certain points in time is called a temporal graph. 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 talk, I will focus on the concept of a temporal spanner, which is a subgraph of the input temporal graph that preserves temporal connectivity using as few edges (or labels) as possible. In stark contrast with standard graphs, it turns out that linear size spanners, and in fact, even sparse spanners (i.e., spanners with o(n^2) edges) do not always exist in temporal graphs. After presenting basic notions and reviewing these astonishing negative results, I will present some good news as well; namely, sparse spanners always exist in *some* natural classes of temporal graphs. These include the cases when the underlying graph is complete (this talk) or when the labels are chosen at random (subsequent talk). If time permit, I will present two open questions, and discuss some recent attempts at solving them.
Time & Location
Dec 06, 2021 | 02:15 PM
Online via Zoom