Dagstuhl Seminar 23422
Graph Algorithms: Cuts, Flows, and Network Design
( Oct 15 – Oct 20, 2023 )
Permalink
Organizers
- Jason Li (University of California - Berkeley, US)
- Debmalya Panigrahi (Duke University - Durham, US)
- Laura Sanita (TU Eindhoven, NL)
- Thatchaphol Saranurak (University of Michigan - Ann Arbor, US)
Contact
- Andreas Dolzmann (for scientific matters)
- Christina Schwarz (for administrative matters)
Dagstuhl Seminar Wiki
- Dagstuhl Seminar Wiki (Use personal credentials as created in DOOR to log in)
Shared Documents
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
Schedule
- Upload (Use personal credentials as created in DOOR to log in)
Graph algorithms are among the foundational pillars of algorithm design and combinatorial optimization. Two large and successful subareas in graph algorithms are those of fast algorithms for flows/cuts and approximation algorithms for network design. Many of the algorithmic ideas and techniques that are a standard feature of an algorithmist's toolkit today trace their origins to groundbreaking research on problems such as minimum cuts, maximum flows, Steiner trees, and the traveling salesman problem. However, research in these two subfields has largely been independent of one another: connectivity problems such as minimum cuts and maximum flows are typically polynomial-time solvable and the goal is to improve the running time (efficiency) of the algorithms; in contrast, network design problems such as Steiner tree and TSP are NP-hard and the goal is to obtain the best approximation factor in (any) polynomial time. This has meant that the two areas have focused on different sets of technical tools – the former has developed combinatorial (and more recently, continuous) methods aimed at improving running times, while the latter has focused on polyhedral techniques and the use of mathematical programming for obtaining improved approximations.
In recent years, however, this distinction between these two subfields has started to blur, and the two areas have started to move closer to one another. This is for two main reasons: (a) recent progress in foundational questions in each area has crucially relied on structural insights from the other area, and (b) there is growing interest in understanding approximation-efficiency tradeoffs in graph algorithms that go beyond always looking for exact solutions for problems in P and allowing arbitrarily large polynomial running times for NP-hard problems. In this Dagstuhl Seminar, we propose to bring the leading researchers from these two communities of fast flow/cut algorithms and approximation algorithms for network design together for an exchange of ideas and knowledge, and a discussion of the major technical challenges in each research area. As described above, there is a growing body of literature that cross-pollinates ideas across these two fields to make progress on longstanding questions. We hope that the seminar will lead to further synergistic progress in both areas, either through direct collaborations, or by making each community aware of the existing knowledge and technical expertise in the other community.

- Amir Abboud (Weizmann Institute - Rehovot, IL) [dblp]
- Greg Bodwin (University of Michigan - Ann Arbor, US) [dblp]
- Parinya Chalermsook (Aalto University, FI) [dblp]
- Shiri Chechik (Tel Aviv University, IL) [dblp]
- Michael Dinitz (Johns Hopkins University - Baltimore, US) [dblp]
- Gramoz Goranci (ETH Zürich, CH) [dblp]
- Fabrizio Grandoni (SUPSI - Lugano, CH) [dblp]
- Anupam Gupta (Carnegie Mellon University - Pittsburgh, US) [dblp]
- Felix Hommelsheim (Universität Bremen, DE) [dblp]
- Robert Krauthgamer (Weizmann Institute - Rehovot, IL) [dblp]
- Alexandra Lassota (MPI für Informatik - Saarbrücken, DE)
- Jason Li (University of California - Berkeley, US) [dblp]
- Yang P. Liu (Institute for Advanced Study - Princeton, US)
- Kurt Mehlhorn (MPI für Informatik - Saarbrücken, DE) [dblp]
- Danupon Nanongkai (MPI für Informatik - Saarbrücken, DE) [dblp]
- Alantha L. Newman (Grenoble INP, FR) [dblp]
- Debmalya Panigrahi (Duke University - Durham, US) [dblp]
- Merav Parter (Weizmann Institute - Rehovot, IL) [dblp]
- Kent Quanrud (Purdue University - West Lafayette, US) [dblp]
- Harald Räcke (TU München - Garching, DE) [dblp]
- Laura Sanita (TU Eindhoven, NL) [dblp]
- Thatchaphol Saranurak (University of Michigan - Ann Arbor, US) [dblp]
- Aaron Sidford (Stanford University, US) [dblp]
- Joachim Spoerhase (University of Sheffield, GB) [dblp]
- Vera Traub (Universität Bonn, DE) [dblp]
- László A. Végh (London School of Economics & Political Science, GB) [dblp]
- Sorrachai Yingchareonthawornchai (University of California - Berkeley, US) [dblp]
- Rico Zenklusen (ETH Zürich, CH) [dblp]
Classification
- Data Structures and Algorithms
Keywords
- graph algorithm
- approximation
- maximum flow
- minimum cut
- network design