TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 23422

Graph Algorithms: Cuts, Flows, and Network Design

( Oct 15 – Oct 20, 2023 )

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/23422

Organizers

Contact

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.

Copyright Jason Li, Debmalya Panigrahi, Laura Sanita, and Thatchaphol Saranurak

Classification
  • Data Structures and Algorithms

Keywords
  • graph algorithm
  • approximation
  • maximum flow
  • minimum cut
  • network design