https://www.dagstuhl.de/23422

October 15 – 20 , 2023, Dagstuhl Seminar 23422

Graph Algorithms: Cuts, Flows, and Network Design

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)

For support, please contact

Christina Schwarz for administrative matters

Andreas Dolzmann for scientific matters

Motivation

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.

Motivation text license
  Creative Commons BY 4.0
  Jason Li, Debmalya Panigrahi, Laura Sanita, and Thatchaphol Saranurak

Classification

  • Data Structures And Algorithms

Keywords

  • Graph algorithm
  • Approximation
  • Maximum flow
  • Minimum cut
  • Network design

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.