In this one-week seminar, recent advances in the area of temporal graphs will be presented, discussed, and some of the current key challenges will be highlighted to better understand the many facets of the computational complexity of temporal graph problems. As this research area grows and broadens internationally, our aim is to bring together people from the various theoretical and practical sub-communities of temporal graphs in order to establish new and to strengthen existing links between these communities. We plan to structure the seminar into four key areas (partially overlapping):

Temporal Graph Theory: Classes and Parameters. Temporal graph problems notoriously turn out to be NP-hard, which is not surprising given the additional complexity added by the temporal dimension. A canonical way to approach such problems is identifying restrictions on the input temporal graphs that allow for polynomial-time algorithms or parameters of the input instances that allow for so-called FPT or XP algorithms. This area focuses on developing new methodology for this approach.

The over-arching goal of this research area is to make progress in developing an algorithmic temporal graph theory, similar to the algorithmic theory on static graphs, taking into account the inherent presence of the time dimension.

Temporal Graph Problems: Algorithms and Structural Results. The goal of this area is to make progress in investigating the computational complexity (both in terms of approximability and parameterized complexity) and structural properties of concrete temporal graph problems. There is an extensive literature on generalizations from classic optimization problems on static graphs to temporal graphs.

Many notions and algorithms on static (i.e., non-temporal) graphs can be naturally transferred in a meaningful way to their temporal counterpart, while in other cases new approaches are needed to define the appropriate temporal notions. We note that, in most cases, the existence of the time dimension adds some degree of freedom in defining a specific temporal variant of a static problem. The most classical example is the temporal analogue of a “shortest path” between two vertices, which can be translated as (a) the topologically shortest path, having the smallest number of edges, (b) the fastest path, having the smallest time duration, or (c) the foremost path, arriving as early as possible (regardless of the starting time). The variety of temporal analogues of static graph optimization problems naturally leads to fundamental algorithmic questions which are still far from being well understood.

Distributed Aspects. The study of the impact of the highly dynamic topology has led the distributed algorithms community to define a number of classes of temporal (or ``time-varying'') graphs that capture various levels of regularities a graph may satisfy over time, regardless of its structure at any single instant. For example, is the schedule of the edges periodic? Do the edges reappear eventually or within bounded time? Is temporal connectivity satisfied infinitely often? Within bounded time? At least once? Does a node meet all the others at least once? Do the edges appear deterministically or randomly? Some of these properties relate to graphs whose lifetime is finite, others to graphs whose lifetime is infinite.

Applications and Algorithm Engineering. In this key area, we will work on identifying the structural properties of temporal graphs that are obtained from data sets as well as from the specific application problems of these application areas. We will investigate possibilities to formalize these properties in terms of temporal graph classes and temporal graph parameters. The goal is to obtain application-driven restrictions of the input instances that allow for efficient algorithms. A starting point for this could be our open-source C++ library TGLib, which integrates efficient data structures and algorithms for temporal graph analysis. At the same time, the findings of the workshop could be integrated into TGLib.

Creative Commons BY 4.0

George B. Mertzios, Hendrik Molter, Petra Mutzel, and Paul Spirakis