The field of dynamic graph algorithms has evolved rapidly over the past decade. New techniques, new problems, new lower bounds, and new approaches have yielded an extremely fruitful research environment. This seminar provided a venue for the community to establish the main challenges that remain and to actively shape the direction of the field going forward.
The seminar brought together the leading researchers and "rising stars" of the field as well as experts in "neighboring" areas such as distributed algorithms, parallel algorithms, streaming algorithms, online algorithms, approximation algorithms, data structures, fine-grained and parameterized complexity, and optimization. Many participants were also actively researching algorithms engineering for dynamic graph problems, which added interesting perspectives on the prevalent theory-practice gap and fundamental methodological challenges.
Several participants gave talks that were highlighting "cutting-edge" advances in the field, including results that very recently appeared in top theory venues such as STOC, FOCS and SODA (and in some cases won the best paper award). Some participants explored connections to other related areas in algorithms research such as distributed and streaming algorithms or differential privacy. Many of the talks also included suggestions on future directions and highlighted the main challenges in the area.
In two open problem sessions, the participants explicitly identified several central open problems that continue to resist progress. We hope that the resulting list of open problems will be a valuable resource for future research in this field.
During and after the sessions, attendees participated in vibrant discussions. Such interactions enhanced the overall experience and made a clear distinction to a traditional conference-like format. In addition to the research activities, there were many social activities (such as board games, poker, music night, hiking, and ping pong) that made the workshop also a great networking opportunity, in particular for the relatively large fraction of participants who were first-time visitors to Schloss Dagstuhl.
The organizers would like to thank Yasamin Nazari and Nicole Wein for helping edit this report, Monika Henzinger for helping develop the concept of this seminar, and the Dagstuhl team for their first-rate support.
The field of dynamic graph algorithms studies algorithms for processing graphs that are changing over time. Formally, the goal is to process an interleaved sequence of update and query operations, where an update operation changes the input graph (e.g. inserts/deletes an edge), while the query operation is problem-specific and asks for some property of the current graph – for example, an s-t path, or a minimum spanning tree. The field has evolved rapidly over the past decade, and this Dagstuhl Seminar will bring together leading researchers in dynamic algorithms and related areas of graph algorithms. Some specific goals for the seminar are outlined below.
- Because the field has grown so much in recent years, one of the main motivations for this seminar is to establish the main challenges that remain – both a list of specific open problems that continue to resist progress, as well as a discussion of more general limitations to our current upper and lower bound techniques. The seminar will also provide a venue for the community to actively shape the direction of the field going forward.
- Much of the recent progress in the field has stemmed from a new set of techniques, many of which originated in other areas of graph or approximation algorithms. One of the goals of this seminar is thus to discuss how recent developments in graph algorithms broadly construed can be applied to the dynamic setting in particular, and to disseminate some of the recent techniques that have already had tremendous success in this regard. To this end, we will organize several tutorials from top experts in the field.
- The experimental evaluation of dynamic graph algorithms is still in its infancy. There are no established data sets or even evaluation methodologies. This seminar aims to include the leading researchers in the area of algorithms engineering of dynamic graph algorithms to address and, hopefully, resolve these fundamental questions.
- Amir Abboud (Weizmann Institute - Rehovot, IL) [dblp]
- Aaron Bernstein (Rutgers University - New Brunswick, US) [dblp]
- Sayan Bhattacharya (University of Warwick - Coventry, GB) [dblp]
- Joakim Blikstad (KTH Royal Institute of Technology - Stockholm, SE) [dblp]
- Karl Bringmann (Universität des Saarlandes - Saarbrücken, DE) [dblp]
- Keren Censor-Hillel (Technion - Haifa, IL) [dblp]
- Shiri Chechik (Tel Aviv University, IL) [dblp]
- Keerti Choudhary (Indian Institute of Technology - New Dehli, IN) [dblp]
- Aleksander Christiansen (Technical University of Denmark - Lyngby, DK)
- Jeremy Fineman (Georgetown University - Washington, DC, US) [dblp]
- Nick Fischer (MPI für Informatik - Saarbrücken, DE)
- Sebastian Forster (Universität Salzburg, AT) [dblp]
- Pawel Gawrychowski (University of Wroclaw, PL) [dblp]
- Gramoz Goranci (ETH Zürich, CH) [dblp]
- Fabrizio Grandoni (SUPSI - Lugano, CH) [dblp]
- Kathrin Hanauer (Universität Wien, AT) [dblp]
- Adam Karczmarz (University of Warsaw - Warsaw, PL & and IDEAS NCBR - Warsaw, PL) [dblp]
- Peter Kiss (University of Warwick - Coventry, GB)
- Tsvi Kopelowitz (Bar-Ilan University - Ramat Gan, IL) [dblp]
- William Kuszmaul (MIT - Cambridge, US) [dblp]
- Jakub Lacki (Google - New York, US) [dblp]
- Nicole Megow (Universität Bremen, DE) [dblp]
- Matthias Mnich (TU Hamburg, DE) [dblp]
- Shay Mozes (Reichman University - Herzliya, IL) [dblp]
- Danupon Nanongkai (MPI für Informatik - Saarbrücken, DE) [dblp]
- Yasamin Nazari (Universität Salzburg, AT) [dblp]
- Nikos Parotsidis (Google Research - Zürich, CH) [dblp]
- Richard Peng (University of Waterloo, CA) [dblp]
- Maximilian Probst Gutenberg (ETH Zürich, CH) [dblp]
- Eva Rotenberg (Technical University of Denmark - Lyngby, DK) [dblp]
- Piotr Sankowski (IDEAS NCBR & University of Warsaw) [dblp]
- Thatchaphol Saranurak (University of Michigan - Ann Arbor, US) [dblp]
- Christian Schulz (Universität Heidelberg, DE) [dblp]
- Chris Schwiegelshohn (Aarhus University, DK) [dblp]
- Shay Solomon (Tel Aviv University, IL) [dblp]
- Clifford Stein (Columbia University, US) [dblp]
- David Tench (Rutgers University - Piscataway, US)
- Jan van den Brand (Georgia Institute of Technology - Atlanta, US)
- Virginia Vassilevska Williams (MIT - Cambridge, US) [dblp]
- David Wajc (Stanford University, US) [dblp]
- Oren Weimann (University of Haifa, IL) [dblp]
- Nicole Wein (Rutgers University - Piscataway, US) [dblp]
- Uri Zwick (Tel Aviv University, IL) [dblp]
- Data Structures and Algorithms
- graph algorithms
- dynamic graphs