Graph Algorithms: Cuts, Flows, and Network Design

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.

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.

We initiate the study of matroid problems in a new oracle model called dynamic oracle. Our algorithms in this model lead to new bounds for some classic problems, and a “unified” algorithm whose performance matches previous results developed in various papers. We also show a lower bound that answers some open problems from a few decades ago. We show an algorithm with $\tilde{O}(n+r\sqrt{r})$ dynamic-rank-query and time complexities for the matroid union problem. This implies an improvement over the traditional rank-query complexity for matroid union. As an interesting special case, it is the first algorithm which, in sufficiently dense graphs, achieves nearly linear time $\tilde{O}(m+n\sqrt{n})$ for the problem of finding k disjoint spanning trees in a graph. We also show simple super-linear $(\mathrm{\Omega }(n\log n))$ query lower bounds for matroid intersection in our dynamic-rank-oracle and the traditional independence-query models; the latter improves the previous $\log 2(3)n-o(n)$ bound.

The girth problem as a central open question in extremal combinatorics, which asks to determine the maximum possible number of edges in an n-node graph whose girth (shortest cycle length) is larger than k. In 1993, a seminal work of Althöfer, Das, Dobkin, Joseph, and Soares showed that determining the size/stretch tradeoff available to graph spanners is equivalent to settling the girth problem. This set in motion a line of research that seeks to understand sparse graph structures by analyzing their forbidden patterns, and using these patterns to invoke ideas from extremal combinatorics.

This talk will survey some successes of the method, including other objects that can also be reduced to the girth problem (distance oracles, fault-tolerant spanners), and related problems that capture other objects in network design, such as the weighted girth problem (light spanners), the bipartite girth problem (distance preservers, reachability preservers), the forbidden biclique problem (directed distance preservers), and the bridge girth problem (reachability preservers, flow-cut gaps). We will survey the common technical threads in these arguments, and overview the many open problems that remain.

We study the Densest Subgraph problem under the additional constraint of differential privacy. In the LEDP (local edge differential privacy) model, introduced recently by Dhulipala et al. [FOCS 2022], we give an $(ϵ,\delta )$-differentially private algorithm with no multiplicative loss: the loss is purely additive. This is in contrast to every previous private algorithm for densest subgraph (local or centralized), all of which incur some multiplicative loss as well as some additive loss. Moreover, our additive loss matches the best-known previous additive loss (in any version of differential privacy) when $1/\delta$ is at least polynomial in $n$, and in the centralized setting we can strengthen our result to provide better than the best-known additive loss. Additionally, we give a different algorithm that is $ϵ$-differentially private in the LEDP model which achieves a multiplicative ratio arbitrarily close to 2, along with an additional additive factor. This improves over the previous multiplicative 4-approximation in the LEDP model. Finally, we conclude with extensions of our techniques to both the node-weighted and the directed versions of the problem.

In this talk, I will explain how to dynamically maintain j-trees and discuss some of the implications of this result.

Given an undirected graph G, the 2-edge-connected spanning subgraph problem is to compute a subgraph $S$ of $G$ with the minimum possible number of edges which is 2-edge-connected, i.e., removing any edge from $S$ leaves a connected graph (spanning all the nodes). The 2-vertex-connected spanning subgraph problem is defined similarly w.r.t. 2-vertex-connectivity. In this talk I will illustrate some recent progress on approximation algorithms for these two problems.

An alpha-approximate universal Steiner tree (UST) of a graph G is a spanning tree T such that, for any vertex terminal subset S, the minimal subtree of T connecting S is within an alpha factor of the cost of the cheapest Steiner tree in G connecting S. Alpha-approximate USTs immediately give alpha-approximations for well-studied variants of Steiner tree such as online or oblivious Steiner tree. Sub-linear-approximate USTs are known but neither the existence of nor poly-time algorithms for computing poly-logarithmic-approximate USTs were previously known.

In this talk, I will discuss the first construction of poly-logarithmic USTs. The result is based on new constructions of poly-logarithmic-quality graph hierarchies called strong sparse partitions which may be interesting in their own right. Roughly, strong sparse partitions provide deterministic guarantees on how often balls of particular radii are cut.

We present recent progress on the problem of computing all-pairs minimum cuts, and more generally the Gomory-Hu tree of a graph. In particular, we obtain the first running time improvement since Gomory and Hu’s original algorithm in 1961, as well as a subsequent improvement to almost-linear time, resolving the complexity of this problem. We discuss important tools that paved the way for the discovery of the algorithm, most notably the isolating cuts problem and a reduction to single-source minimum cut.

We discuss extensions of the recent almost-linear-time maximum flow and mincost flow algorithm to dynamic and deterministic settings. Joint work with Jan van den Brand, Li Chen, Rasmus Kyng, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, and Aaron Sidford.

A set of indivisible goods is to be allocated to a group of agents, e.g, a car, a computer, a tooth-brush. Each agent has a valuation over sets of goods. There are only two restrictions on a valuation. The value of the empty set is zero and more is better. We want to a allocate the goods in a fair manner. Three notions of fairness have emerged: envy-freeness, fair share, and maximum Nash-value. We discuss exact and approximate existence and complexity.

Some of the algorithm have a strong connection to matchings.

Given a weighted graph $G$, a hopset of hopbound $\beta$ and stretch $(1+ϵ)$ is a set of edges such that for any pair of nodes $u$ and $v$ in $G$, there is a path in $G\cup H$ of at most $\beta$ hops whose length is within a $(1+ϵ)$ factor of the distance between u and v in G. Hopsets have recently found many applications in fast distance computation in various computational models such as dynamic, parallel and distributed models. This talk gives an introduction to hopsets for undirected graphs and their algorithmic applications in these settings. We conclude with open problems on applications of directed hopsets.

We present a new efficient decomposition lemma for tournaments, which we use to design polynomial-time algorithms to color various classes of tournaments with few colors, notably, to color a 2-colorable tournament with ten colors. We also use this lemma to prove equivalence between the problems of coloring 3-colorable tournaments and coloring 3-colorable graphs with constantly many colors. For the classes of tournaments considered, we complement our upper bounds with strengthened lower bounds, painting a comprehensive picture of the algorithmic and complexity aspects of coloring tournaments.

Graph sparsification has been an important topic with many structural and algorithmic consequences. Recently hypergraph sparsification has come to the fore and has seen exciting progress. In this paper we take a fresh perspective and show that they can be both be derived as corollaries of a general theorem on sparsifying matroids and monotone submodular functions.

Quotients of matroids and monotone submodular functions generalize $k$-cuts in graphs and hypergraphs. We show that a weighted ground set of a monotone submodular function $f$ can be sparsified while approximately preserving the weight of every quotient of $f$ with high probability in randomized polynomial time.

This theorem conceptually unifies cut sparsifiers for undirected graphs [BK15] with other interesting applications. One basic application is to reduce the number of elements in a matroid while preserving the weight of every quotient of the matroid. For hypergraphs, the theorem gives an alternative approach to the hypergraph cut sparsifiers obtained recently in [CKN20], that also preserves all $k$-cuts. Another application is to reduce the number of points in a set system while preserving the weight of the union of every collection of sets. We also present algorithms that sparsify hypergraphs and set systems in nearly linear time, and sparsify matroids in nearly linear time and queries in the rank oracle model.

The Isolating Mincuts algorithm is a new technique recently introduced by [Li and Panigrahi] and [Abboud Krauthgamer Trabelsi]. In the last three years, they found more than ten applications in fast graph algorithms. I will give a gentle tutorial on this technique.

Maintaining an approximately maximum matching in a dynamic graph is a fundamental problem in data structures and algorithmic graph theory. In this talk I will discuss recent progress in the special case of decremental bipartite matching, where the only dynamic updates are deleting edges from an initial bipartite graph. In particular, I will discuss how faster runtimes were obtained by reducing this dynamic problem to solving a sequence of natural convex optimization problems.

Augmentation problems are a fundamental class of network design problems. They ask about the cheapest way to increase the (edge-)connectivity of a graph by adding edges among a given set of options. One of the most elementary and intensely studied augmentation problems is the (Weighted) Tree Augmentation Problem. Here, a spanning tree has to be augmented into a 2-edge-connected graph.

Classic techniques for network design yield 2-approximation algorithms for a wide class of augmentation problems. For the Unweighted Tree Augmentation Problem, better-than-2 approximations are known for more than 20 years. However, only recently the first better-than-2 approximations have been found for the more general Unweighted Connectivity Augmentation Problem and Weighted Tree Augmentation Problem. In this talk we will discuss these recent advances.

Deterministic algorithms, unfortunately, have remained much slower even if we assume a linear-time max-flow algorithm: they either require at least $\mathrm{\Omega }(mn)$ time [Even’75; Henzinger Rao and Gabow, FOCS’96; Gabow, FOCS’00] or assume that $k=o(\sqrt{\log n})$ [Saranurak and Yingchareonthawornchai, FOCS’22]. In this talk, I will describe a deterministic algorithm for checking $k$-vertex connectivity in time proportional to making $\min \{k^2,n\}$ max-flow calls, and, hence, in $\widehat{O}(m\min \{k^2,n\})$ time using the deterministic max-flow algorithm by [Brand et al. FOCS’23]. Our algorithm gives the first almost-linear-time bound for all $k$ where $\sqrt{\log n}\le k\le n^{o(1)}$ and subsumes up to a sub-polynomial factor the long-standing state-of-the-art algorithm by [Even’75] which requires $O(n+k^2)$ max-flow calls. For large $k$, the algorithm runs in $\widehat{O}(mn)$ time, which improves over the state-of-the-art deterministic $\widehat{O}(m{n}^{1.5})$-time algorithm [Gabow, FOCS’00]. Our key technique is based on Ramanujan expanders and derandomization of the kernelization technique of [Li et al. STOC’21] for which their kernel construction was randomized.