Dagstuhl-Seminar 21171
Temporal Graphs: Structure, Algorithms, Applications
( 25. Apr – 30. Apr, 2021 )
Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:
https://www.dagstuhl.de/21171
Organisatoren
- Arnaud Casteigts (University of Bordeaux, FR)
- Kitty Meeks (University of Glasgow, GB)
- George B. Mertzios (Durham University, GB)
- Rolf Niedermeier (TU Berlin, DE)
Kontakt
- Shida Kunz (für wissenschaftliche Fragen)
- Simone Schilke (für administrative Fragen)
Impacts
- Counting Temporal Paths - Enright, Jessica; Meeks, Kitty; Molter, Hendrik - Cornell University : arXiv.org, 2022. - 48 pp..
- Giant Components in Random Temporal Graphs : article - Becker, Ruben; Casteigts, Arnaud; Crescenzi, Pierluigi; Kodric, Bojana; Raskin, Michael; Zamaraev, Viktor; Renken, Malte - Cornell University : arXiv.org, 2022. - 26 pp..
Programm
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.
Creative Commons BY 3.0 DE
Arnaud Casteigts, Kitty Meeks, George B. Mertzios, and Rolf Niedermeier
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. 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 such dynamically changing graphs the notion of vertex adjacency needs to be revisited and various graph concepts, e.g., reachability and connectivity, now crucially depend on the exact temporal ordering of the edges' presence. Furthermore, the rate and/or degree of the changes is generally too high to be reasonably modeled in terms of network faults or failures: in these systems changes are not anomalies but rather an integral part of the nature of the system.
A temporal graph is a graph which changes over time. Although many different variations for the model of temporal graphs exist, the most common one concerns graphs whose vertex set is fixed while the edge set changes over time. According to this model, 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 transferred in a natural way to their temporal counterpart, while in other cases new approaches are needed to define the appropriate temporal notions. 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 purpose of this one-week seminar was to present and discuss recent advances in the area of temporal and dynamically changing graphs, and to identify and highlight some of the current key challenges to better understand the multiple facets of the computational complexity of temporal graph problems. The seminar was mostly rooted in the rich and mature experience with algorithmic problems on static (i.e., traditional) graphs and in the general quest to understand the computational complexity of temporal versions of fundamental graph problems and algorithms.
Four key areas had been identified, which constituted the backbone of the seminar:
- Models, Concepts, Classes. Transferring problems from static to temporal graphs in a meaningful way is a challenging task, with potentially several well-motivated models in the temporal setting corresponding to the same static graph problem. Since temporal graph problems are notoriously hard, a natural way to approach this issue is to restrict input instances. One of the most immediate ways to restrict inputs (which originates in the static algorithmic graph theory) is to restrict the family of underlying graphs G. However, in temporal graphs, the temporal dimension offers so much structure that one can encode hard problems without the need of a sophisticated structure in the underlying graph or in any single layer. This observation suggests that restrictions of the “temporal pattern”, i.e., of the way in which the time-labels appear (either alone or in combination with the above mentioned restrictions) can often help to identify tractable special cases of temporal graph problems.
- Concrete Algorithmic Problems. There are many examples of canonical generalizations from classic optimization problems on static graphs to temporal graphs. The most meaningful way in which a temporal version of a classic optimization problem may be defined crucially depends on the underlying application domain. Generally, temporal variants tend to become computationally harder than the corresponding classic optimization problem. Canonical ways to tackle the computational hardness are to (i) restrict the input instances to certain graph classes that allow for efficient (exact) algorithms or find parameters that allow for fixed-parameter algorithms, (ii) aiming for polynomial-time approximation algorithms where a certain level of solution quality is guaranteed, or (iii) combining (i) and (ii).
- Distributed Aspects. A common approach to analyzing distributed algorithms is the characterization of necessary and sufficient conditions to their success. These conditions commonly refer to the communication model, synchronicity, or structural properties of the network (e.g., is the topology a tree, a grid, a ring, etc.) In a highly-dynamic network, the topology changes during the computation, and this may have a dramatic effect on computation. The study of this impact has led the distributed algorithms community to define a number of classes of temporal graphs that capture various levels of regularities a graph may satisfy over time, regardless of its structure at any single instant. It turns out that some of these properties – in particular the ones pertaining to finite time – are also relevant in a (centralized) algorithmic setting and have an impact on the computational complexity (or feasibility) of classic problems. In particular, properties like periodicity, temporal connectivity, and bounded temporal diameters have been considered both in the distributed and in the non-distributed settings. The seminar played here a crucial role in allowing the different communities to meet and share their complementary experience of temporal properties, as well as to converge on terminology and modeling aspects.
- Applications. Whenever there is a situation with pairwise interactions and information about the time point when these interactions happen, the framework of temporal graphs offers a natural mathematical model. This is especially the case in applications where the time information is critical. Examples include traffic and transportation networks, social network analysis (especially when analyzing disease or rumor spreading phenomena), biological networks, mobile sensor networks, and neural networks. All these application areas have their own problem settings and problem instances with specific properties and, in order to apply the fast-developing theory of algorithms for temporal graphs, it is essential to identify and formalise the properties of temporal graphs derived from data sets in these application areas, with the goal of obtaining application-driven restrictions of the input instances that allow for efficient algorithms. Among other application-oriented talks, the seminar included two highly topical talks relating to the role of temporal graphs in pandemic modelling.
The Dagstuhl Seminar 21171 "Temporal Graphs: Structure, Algorithms, Applications" brought together 53 participants from 13 different countries in Europe, USA, Japan, and Israel. The list of participants and speakers contained international experts in algorithms and complexity, social networks and computational social choice, complex systems, distributed algorithms, and parameterized algorithmics. We had in total 21 talks, each of approximately 30 minutes duration, and two sessions where open problems were proposed and discussed.
As this Dagstuhl Seminar was held entirely online (which would be unheard of a few years ago), we provided access to all participants to the online platform GatherTown which enabled us to virtually interact in a way which simulated (very satisfactory) physical meetings and interaction (e.g., also having virtual boards at our disposal). We had the GatherTown platform open every day all day (from the morning until the night), while we specified slots of 2-hours daily where everybody was expected to come to GatherTown. The rest of the day, GatherTown was there to facilitate all people who wanted to have extended physical-looking scientific meetings. During the Seminar, collaborative work was encouraged over all formal and informal scientific discussions. By building on the pre-existing synergies between the participating researchers, new collaborations have been initiated and old ones have been reinforced, and this across all all the communities which were represented in the Seminar.
To conclude, this Seminar has been successful in bringing together scientists from different backgrounds and initiating or strengthening research collaborations on the wide topic of temporal and dynamically changing graphs. Last, but not least, these collaborations and scientific discussions presented a fruitful mix between young researchers, such as PhD students, with older and established researchers in the general field of temporal graphs.
We would like to express our special gratitude to the team of Schloss Dagstuhl who were extremely supportive and also flexible on how to organize a virtual Dagstuhl Seminar during these unprecedented times of the pandemic, without compromising the scientific quality and the overall participation experience of the Seminar.
Acknowledgments
The organizers are very grateful to Hendrik Molter and Malte Renken (TU Berlin) for helping in organizing the seminar (program compilation, technical support during the seminar, etc.) and to William Petterson and John Sylvester (University of Glasgow) for their help in collecting the material and compiling this report.
Arnaud Casteigts, Kitty Meeks, George B. Mertzios, and Rolf Niedermeier
Remote:
- Evripidis Bampis (Sorbonne University - Paris, FR)
- Julien Baste (University of Lille, FR)
- Prithwish Basu (BBN Technologies - Cambridge, US)
- Cristiano Bocci (University of Siena, IT)
- Hans L. Bodlaender (Utrecht University, NL) [dblp]
- Binh-Minh Bui-Xuan (UPMC - Paris, FR)
- Benjamin Bumpus (University of Glasgow, GB)
- Chiara Capresi (University of Siena, IT)
- Arnaud Casteigts (University of Bordeaux, FR) [dblp]
- Rémy Cazabet (University of Lyon, FR)
- Andrea Clementi (University of Rome "Tor Vergata", IT) [dblp]
- Timothée Corsini (University of Bordeaux, FR)
- Pierluigi Crescenzi (Gran Sasso Science Institute, IT) [dblp]
- Jessica Enright (University of Glasgow, GB)
- Thomas Erlebach (University of Leicester, GB) [dblp]
- Bruno Escoffier (Sorbonne University - Paris, FR)
- Till Fluschnik (TU Berlin, DE) [dblp]
- Samuel Hand (University of Glasgow, GB)
- Petter Holme (Tokyo Institute of Technology, JP)
- Frank Kammer (THM - Gießen, DE)
- Mikko Kivelä (Aalto University, FI) [dblp]
- Ralf Klasing (CNRS and University of Bordeaux, France)
- Christian Komusiewicz (Universität Marburg, DE) [dblp]
- Michael Lampis (University Paris-Dauphine, FR) [dblp]
- Zvi Lotker (Bar-Ilan University, IL)
- Andrea Marino (Univerisità degli Studi di Firenze, IT) [dblp]
- Kitty Meeks (University of Glasgow, GB) [dblp]
- Nicole Megow (Universität Bremen, DE) [dblp]
- George B. Mertzios (Durham University, GB) [dblp]
- Othon Michail (University of Liverpool, GB) [dblp]
- Hendrik Molter (TU Berlin, DE)
- Vincenzo Nicosia (Queen Mary University of London, GB)
- Rolf Niedermeier (TU Berlin, DE) [dblp]
- William Pettersson (University of Glasgow, GB) [dblp]
- Yoann Pigné (University of Le Havre, FR)
- Michael Raskin (TU München, DE) [dblp]
- Malte Renken (TU Berlin, DE)
- Eric Sanlaville (University of Le Havre, FR)
- Jason Schoeters (University of Bordeaux, FR)
- Fiona Skerman (Uppsala University, SE) [dblp]
- Martin Skutella (TU Berlin, DE) [dblp]
- Manuel Sorge (TU Wien, AT)
- Paul Spirakis (University of Liverpool, GB) [dblp]
- Jakob Spooner (University of Leicester, GB)
- Ondrej Suchý (Czech Technical University - Prague, CZ) [dblp]
- John Sylvester (University of Glasgow, GB)
- Nikolaj Tatti (University of Helsinki, FI) [dblp]
- Amitabh Trehan (Durham University, GB)
- Mathilde Vernet (University of Le Havre, FR)
- Tiphaine Viard (Telecom Paris, FR)
- Viktor Zamaraev (University of Liverpool, GB) [dblp]
- Christos Zaroliagis (University of Patras, GR) [dblp]
- Philipp Zschoche (TU Berlin, DE)
Klassifikation
- Data Structures and Algorithms
- Discrete Mathematics
- Social and Information Networks
Schlagworte
- Models and Classes
- Complex Network Analysis
- Parameterized Complexity Analysis
- Algorithm Engineering
- Distributed Computing
