Graph algorithms are among the foundational pillars of algorithm design and combinatorial optimization. In addition to its significance as a theoretical discipline, graph algorithms are also ubiquitous in practice, with applications in essentially every scientific discipline. This has spawned research in many different directions within graph algorithms over the past few decades, and these individual research areas have come to play important roles in the evolution of algorithms research as a whole. Two particularly large and successful subdisciplines are those of fast algorithms for flows and 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 in these two areas spanning problems such as minimum cuts, maximum flows, Steiner trees, and the traveling salesman problem. The last few years, in particular, have been truly outstanding in achieving progress on longstanding questions in both areas. Some of the highlights include the first progress in decades for problems such as the traveling salesman problem (e.g., [20, 19, 17, 28, 34]), graph connectivity augmentation (e.g., [9, 10, 35]), minimum cut (e.g., [24, 11]), vertex connectivity (e.g., [23]), all-pairs minimum cuts (e.g., [3, 2, 5, 4, 6, 25, 26, 1]), and last but not the least, the recent breakthrough achieving an almost linear-time algorithm for maximum flow (and minimum cost flow) [12] (see also [14, 16, 37, 36]).

Traditionally, to a large extent, research in these two subfields has progressed independent of one another: connectivity problems such as minimum cuts and maximum flows are typically polynomial-time solvable and 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 the two subfields has started to blur, and the 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. For example, one of the main new ingredients in the recent breakthrough results in approximation algorithms for the traveling salesman problem (e.g., [20, 17]) is a better understanding of the structure of near-minimum cuts (e.g., [7]) in an undirected graph. Or, recent work in the all-pairs minimum cuts problem [1] that advances the state of the art for this problem after 60 years crucially makes use of Steiner tree approximations [27]. Or, cut matching games originally devised for sparsest cut approximations [22] have led to fast expander decompositions (e.g., [30]) that, in turn, play a crucial role in recent progress in deterministic minimum cut algorithms [24].

(b)

There is growing interest in understanding approximation-efficiency tradeoffs in graph algorithms. Graph sparsification (e.g., [8, 15, 32, 33]) has emerged as a standard tool that “compresses” an arbitrary graph into a sparse subgraph (called the sparsifier) while approximately preserving the values of all cuts in the graph. This naturally leads to an approximation-efficiency tradeoff by running existing algorithms on the sparsifier rather than on the input graph. But, beyond the black box use of sparsifiers, efficiency at the expense of mild approximation has been employed as a technical tool to breach longstanding running time barrier in recent years, and has often eventually led to faster exact algorithms as well. A famous example is the maximum flow problem in undirected graphs, where nearly-linear time approximation algorithms were designed in the last decade [21, 31, 29] and has eventually resulted in the very recent breakthrough achieving an almost-linear time exact algorithm [12]. Another recent example is the all-pairs minimum cuts problem for which the first paper to breach the 60-year old running time bound of Gomory and Hu [18] incurred a mild approximation [25], but this has now led to a faster exact algorithm as well [1]. Finally, understanding the efficiency-approximation tradeoff is an important goal for NP-hard network design problems such as Steiner tree [27] and Steiner forest [13], and this, in turn, has implications for minimum cut problems [1].

The goal of this seminar was 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.

Seminar Structure and Participants

The seminar brought together 25 researchers from the two communities highlighted above, roughly equally split between the two areas. There was also a mix of senior and junior participants, ranging from senior members of the community to current PhD students and postdoctoral researchers. In terms of gender balance, around 20% of the attendees were female. (The organizers had originally planned for a more equitable balance, but there were several late retractions, primarily due to geopolitical reasons, that affected the gender ratio.)

There were 17 scheduled talks, divided into long (60 minutes) and short (30 minutes) presentations. There was also an open problem session and a panel discussion on the future directions for the community. The schedule left plenty of time for collaboration and free discussion among the participants.

Outcomes

The main objective of the seminar was to provide a forum for the exchange of ideas between the research communities of fast flow/cut algorithms and approximation algorithms for network design. These are adjoining areas where researchers have a working knowledge of, and appreciation for, each other's work. As expected, the seminar lead to cohesive interactions and meaningful discussions. Individual research talks and afternoon breaks created concrete opportunities for learning about recent progress in each other's areas and fostering collaborations. The open problem session highlighted the major research challenges in the two areas, which is particularly beneficial for junior members of the community who attended the seminar. The panel discussion allowed the participants to reflect on and discuss higher-level questions about the research directions that the communities should pursue in the near future. Overall, we believe that the seminar played an important role in community building, research collaborations, and in shaping the two research areas for the foreseeable future.

The organizers would like to thank the Scientific Directorate and the administration of the Dagstuhl Center for their amazing support in the organization of the Dagstuhl Seminar, and for supporting this important research area.

References

1. Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, and Ohad Trabelsi. Gomory-Hu tree in subcubic time. CoRR, abs/2111.04958, 2021.
2. Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi. Cut-equivalent trees are optimal for min-cut queries. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020. IEEE Computer Society, 2020.
3. Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi. New algorithms and lower bounds for all-pairs max-flow in undirected graphs. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5–8, 2020, pages 48–61. SIAM, 2020.
4. Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi. APMF <APSP? Gomory-Hu tree for unweighted graphs in almost-quadratic time. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7–10, 2022, pages 1135–1146. IEEE, 2021.
5. Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi. Subcubic algorithms for Gomory- Hu tree in unweighted graphs. In Samir Khuller and Virginia Vassilevska Williams, editors,STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21–25, 2021, pages 1725–1737. ACM, 2021.
6. Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi. Friendly cut sparsifiers and faster gomory-hu trees. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9–12, 2022, pages 3630–3649. SIAM, 2022.
7. András A Benczúr. A representation of cuts within 6/5 times the edge connectivity with applications. In Proceedings of IEEE 36th Annual Foundations of Computer Science, pages 92–102. IEEE, 1995.
8. András A. Benczúr and David R. Karger. Randomized approximation schemes for cuts and flows in capacitated graphs. SIAM J. Comput., 44(2):290–319, 2015.
9. Jaroslaw Byrka, Fabrizio Grandoni, and Afrouz Jabal Ameli. Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 815–825, 2020.
10. Federica Cecchetto, Vera Traub, and Rico Zenklusen. Bridging the Gap between Tree and Connectivity Augmentation: Unified and Stronger Approaches, page 370–383. Association for Computing Machinery, New York, NY, USA, 2021.
11. Ruoxu Cen, Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, and Kent Quanrud. Minimum cuts in directed graphs via partial sparsification. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7–10, 2022, pages 1147–1158. IEEE, 2021.
12. Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. CoRR, abs/2203.00671, 2022.
13. Richard Cole, Ramesh Hariharan, Moshe Lewenstein, and Ely Porat. A faster implementation of the goemans-williamson clustering algorithm. In S. Rao Kosaraju, editor, Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, January 7–9, 2001, Washington, DC, USA, pages 17–25. ACM/SIAM, 2001.
14. Sally Dong, Yu Gao, Gramoz Goranci, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Guanghao Ye. Nested dissection meets ipms: Planar min-cost flow in nearly-linear time. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9–12, 2022, pages 124–153. SIAM, 2022.
15. Wai Shing Fung, Ramesh Hariharan, Nicholas J. A. Harvey, and Debmalya Panigrahi. A general framework for graph sparsification. SIAM J. Comput., 48(4):1196–1223, 2019.
16. Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai. Deterministic graph cuts in subquadratic time: Sparse, balanced, and k-vertex. arXiv preprint arXiv:1910.07950, 2019.
17. Shayan Oveis Gharan, Amin Saberi, and Mohit Singh. A randomized rounding approach to the traveling salesman problem. In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22–25, 2011, pages 550–559. IEEE Computer Society, 2011.
18. Ralph E Gomory and Tien Chung Hu. Multi-terminal network flows. Journal of the Society for Industrial and Applied Mathematics, 9(4):551–570, 1961.
19. Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. An improved approximation algorithm for TSP in the half integral case. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22–26, 2020, pages 28–39. ACM, 2020.
20. Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. A (slightly) improved approximation algorithm for metric TSP. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21–25, 2021, pages 32–45. ACM, 2021.
21. Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford. An almost-lineartime algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5–7, 2014, pages 217–226, 2014.
22. Rohit Khandekar, Satish Rao, and Umesh V. Vazirani. Graph partitioning using single commodity flows. J. ACM, 56(4):19:1–19:15, 2009.
23. Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai. Vertex connectivity in poly-logarithmic max-flows. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 317–329. ACM, 2021.
24. Jason Li and Debmalya Panigrahi. Deterministic min-cut in poly-logarithmic max-flows. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 85–92. IEEE, 2020.
25. Jason Li and Debmalya Panigrahi. Approximate gomory-hu tree is faster than n – 1 max-flows. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1738–1748. ACM, 2021.
26. Jason Li, Debmalya Panigrahi, and Thatchaphol Saranurak. A nearly optimal all-pairs min-cuts algorithm in simple graphs. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7–10, 2022, pages 1124–1134. IEEE, 2021.
27. Kurt Mehlhorn. A faster approximation algorithm for the Steiner problem in graphs. Information Processing Letters, 27(3):125–128, 1988.
28. Tobias Mömke and Ola Svensson. Approximating graphic TSP by matchings. In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 560–569. IEEE Computer Society, 2011.
29. Richard Peng. Approximate undirected maximum flows in O(mpolylog(n)) time. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1862–1867, 2016.
30. Thatchaphol Saranurak and Di Wang. Expander decomposition and pruning: Faster, stronger, and simpler. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 2616–2635. SIAM, 2019.
31. Jonah Sherman. Nearly maximum flows in nearly linear time. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 263–269. IEEE Computer Society, 2013.
32. Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM J. Comput., 40(6):1913–1926, 2011.
33. Daniel A. Spielman and Shang-Hua Teng. Spectral sparsification of graphs. SIAM J. Comput., 40(4):981–1025, 2011.
34. Vera Traub and Jens Vygen. Approaching 3/2 for the s-t-path TSP. J. ACM, 66(2):14:1– 14:17, 2019.

Creative Commons BY 4.0

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