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.

Creative Commons BY 4.0

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