25.04.21 - 30.04.21, Seminar 21171

Temporal Graphs: Structure, Algorithms, Applications

The following text appeared on our web pages prior to the seminar, and was included as part of the invitation.

Motivation

Traditionally, graphs (composed of vertices and edges) are used to abstractly model diverse real-world systems, where vertices and edges represent elementary system units and some kind of interactions between them, respectively. However, in modern systems, this modeling paradigm using static graphs may be too restrictive or oversimplifying, as interactions often change over time in a highly dynamic manner. For example, friendships are added and removed over time in a social network and links in a communication network may change dynamically, either according to a specific known pattern (satellites following a trajectory) or in an unpredictable manner (mobile ad-hoc networks). The common characteristic in all these application areas is that the system structure, i.e., graph topology, is subject to discrete changes over time. In particular, we are interested in scenarios where we have full information over the changes which happened in the past or will happen in the future. In such dynamically changing graphs the notion of vertex adjacency needs to be revisited and various graph concepts, e.g., reachability and connectedness, now crucially depend on the exact temporal ordering of the edges’ presence.

Correspondingly, a temporal graph is a graph whose edge set changes over time. Given a static underlying graph G, a temporal graph is obtained by assigning to every edge of G a set of nonnegative integer time-labels, indicating the discrete time steps in which this edge is active. 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. For example, depending on the application domain, the temporal analogue of a “shortest path” between two vertices 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. Notably, such topics are temporal in essence, which means that they cannot be defined in terms of the structure of the graph at a given instant.

In this one-week Dagstuhl 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. This research area grows and broadens internationally, and our aim is to bring together people from the various theoretical and practical subcommunities 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). (1) Models, Concepts, Classes, (2) Concrete Algorithmic Problems, (3) Distributed Aspects, and (4) Applications.

License
Creative Commons BY 3.0 DE
Arnaud Casteigts, Kitty Meeks, George B. Mertzios, and Rolf Niedermeier