Congestion-Approximators from the Bottom Up

The famous max-flow min-cut theorem¹¹1For the sake of this introduction, a flow problem on a graph is a set of excesses and deficits on vertices and a solution is a set of paths connecting excess and deficits where no edge is used in more than one path. implies that any set of excesses or deficits in a graph can be connected by disjoint paths if and only if every cut in the graph has more capacity in the edges that cross the cut than the “demand” that is required to cross it. One direction is easy to see (if a cut does not have enough capacity, clearly one cannot route demand paths across it), and the other can be established by linear programming duality (or explicitly using an algorithm as was done by Ford and Fulkerson in 1956 [12].)

Framed slightly differently, a cut where the ratio of the demand across it to the capacity of the cut is $c$ implies that any flow satisfying the demands requires at least $c$ units of flow go through some edge. Again, the max-flow min-cut theorem implies that there is always such a cut if the optimal flow has congestion $c$. Here, the congestion of a flow is the maximum flow that is routed on any edge in the graph.

More generally, the set of feasible demands in a graph is captured by the (exponentially sized) set of all cuts in the graph. Remarkably, it was shown that polynomially many cuts could approximately (within logarithmic factors) characterize the congestion of any set of demands [31, 32]. Indeed, the total size of cuts was nearly-linear²²2Nearly-linear means $O(m\log^{c}n)$ where $c$ is a constant. Almost-linear means $O(m^{1+\epsilon})$ for some $\epsilon=o(1)$. in [31, 33] and could be computed in nearly-linear time as announced in 2014 by Peng [29].

More precisely, an $\alpha$-congestion-approximator for a graph is a set of cuts where for every set of demands, the minimum ratio (over cuts in the $\alpha$-congestion-approximator) of the demands crossing the cut and the capacity of the cut determines the minimum congestion of the optimal flow (that routes the demands) to within an $\alpha$ factor.

In this paper, we provide an $\alpha$-congestion-approximator (along with an routing scheme) that can be constructed in nearly-linear time with an $\alpha$ of $O(\log^{10}n)$. The number of logarithmic factors is not optimized but the structure is significantly simpler than the construction by Peng [29].

The top-down frame of the decomposition of [33] requires that one compute approximate maximum flows at the very top level which entailed a non-linear runtime. A breakthrough result of Sherman [36] showed how to use congestion-approximators to find approximate maximum flows.³³3Simultaneously, Kelner et. al. [17] used a dual version of congestion approximators called oblivous routers to give efficient algorithms for approximate maximum flow. Peng [30] used the result of Sherman [36] inside the top-down partitioning method based on [33] for constructing congestion-approximators. There is a chicken and egg problem here as the two methods need each other, and a costly recursion was used to combine them based on ultra-sparsifiers which we discuss a bit more below.

Our result proceeds in a bottom-up iterative fashion; indeed, the bottom level is a “weak expander decomposition” which can be computed using trivial congestion-approximators consisting of singleton vertices.⁴⁴4We note expander decompositions themselves have found wide application, including in the breakthrough near linear time algorithm of [8] for maximum flow. Also, the high-level idea of our congestion-approximator is similar to hierachical expander decomposition [13], and our techniques may be useful in getting from almost linear to near linear. Then we proceed level by level, using the lower level clusterings as “pseudo”-congestion-approximators for the next. The frame is simple, but “around the edges” both literally (the edges of the clusters) and metaphorically there are technical issues which require some attention.

Still, given the power that congestion-approximators provide with respect to understanding the structure of graphs, finding more efficient constructions is important and an effective bottom-up or clustering approach seems a natural path to follow. We make the first and a substantive step on this path in the decade since the announcement of Peng’s also polylogarithmic nearly linear time algorithm [29].

Recent progress on maximum flow can be compared to developments in nearly-linear time Laplacian solvers [38], which were initially very complex with many logarithmic factors. But over the years, new tools were developed that both improved the running times and allowed for better understanding of graphs as well as having broader application. See, for example, [21, 22, 10, 16]. Progress has been much slower for maximum flow in comparison. Perhaps one reason is that solutions to Laplacian linear systems are $\ell_{2}$ optimizing flows that involve the Euclidean norm which is a fair bit simpler than the $\ell_{\infty}$ norm central to maximum flow or norms based on more general convex bodies. We believe this result to be a step in the process of understanding maximum flows better.

We proceed with a discussion of previous work which consists of a remarkable series of developments.

Our main conceptual and technical contribution is a novel congestion approximator that is constructed bottom-up in a hierarchical fashion. We start with an informal construction in the theorem below, which is later formalized in Theorem 4.1. See Figure 1 for an illustration.

To understand the construction, first consider the case $i=1$. By property (1), $\mathcal{P}_{1}$ is the partition of singleton clusters. Since the inter-cluster edges of $\mathcal{P}_{1}$ are precisely all the edges, property (2) says that for each cluster $C\in\mathcal{P}_{i+1}$, the edges internal to $C$, together with the boundary edges of $C$, “mix” in the graph $G$. In other words, the set of edges with at least one endpoint in $C$ mixes in $G$. In the extreme case $C=V$, the entire edge set mixes in $G$, so the graph $G$ is an expander.⁸⁸8We do not define expanders in this paper since we do not need their precise definition. The connection to expanders is only stated as motivation for readers familiar with the concept. In general, we can informally say that each cluster $C$ is a sort of weak-expander, and the partition $\mathcal{P}_{2}$ is a weak-expander decomposition of graph $G$.⁹⁹9A key difference (from an actual expander decomposition) is that the (routing to certify the) mixing of each cluster is not required to be fully inside its induced subgraph, although the full graph $G$ still needs to have the capacity to support the mixing of all the clusters simultaneously.

Now consider property (3), which establishes a flow starting from the inter-cluster edges of $\mathcal{P}_{2}$ such that each edge in $G$ receives at most half its capacity in flow. We claim that this statement is very natural and follows almost immediately from property (2) with one mild assumption: for each cluster in $\mathcal{P}_{i+1}$, the total capacity of boundary edges is much smaller than the total capacity of internal edges.¹⁰¹⁰10From the perspective of expander decompositions, this assumption is very natural. Expander decompositions require that the total capacity of inter-cluster edges is small relative to the total capacity of all edges. We are simply extending this property to hold for each cluster, not just globally over all clusters. Indeed, from the mixing of the internal and boundary edges of $C$, we can spread a flow from the boundary edges of $C$ such that each internal edge receives flow proportional to its capacity. As long as the boundary edges have small total capacity, the total flow source is also small, so each internal edge receives a small amount of flow relative to its capacity. Finally, since the clusters mix simultaneously, we can compose the corresponding flows for each cluster and still ensure small congestion.

Now consider a general level $i\geq 2$. Recall from property (2) that for each cluster $C\in\mathcal{P}_{i+1}$, the inter-cluster edges of $\mathcal{P}_{i}$ inside $C$, together with the boundary edges of $C$, “mix” in the graph $G$ (see Figure 1, middle). We can interpret this statement (again) as a weak-expander decomposition where expansion is measured with respect to a subset of edges, namely the inter-cluster edges of partition $\mathcal{P}_{i}$ together with the boundary edges of a cluster in $\mathcal{P}_{i+1}$. Property (3) says that we can spread flow from the inter-cluster edges of $\mathcal{P}_{i+1}$ to the inter-cluster edges of $\mathcal{P}_{i}$ such that each edge in $\mathcal{P}_{i}$ receives a small amount of flow (see Figure 1, right). Once again, we can show that it follows from property (2) with the following mild assumption: for each cluster in $\mathcal{P}_{i+1}$, the total capacity of boundary edges is much smaller than the total capacity of inter-cluster edges of $\mathcal{P}_{i}$ that are internal to this cluster.

Overall, the partitions $\mathcal{P}_{1},\mathcal{P}_{2},\ldots,\mathcal{P}_{L}$ can be viewed as hierarchical expander decompositions where each partition $\mathcal{P}_{i+1}$ is a weak-expander decomposition relative to the inter-cluster edges of partition $\mathcal{P}$. It is instructive to compare our partitioning to the expander hierarchy construction of [14], where clusters of the previous partition are contracted before building the next partition. While [14] can also extract a congestion approximator from their expander hierarchy construction, their quality is $n^{o(1)}$ because they lose a multiplicative factor from contracting vertices on each level of the hierarchy. To avoid this multiplicative blow-up per level, we do not contract vertices, so our partitioning is not truly hierarchical: a cluster in partition $\mathcal{P}_{i}$ may be “cut” into many components by the next partition $\mathcal{P}_{i+1}$ (see Figure 1, left). While a hierarchical construction is not required, it is a useful property to have when analyzing the quality of the final congestion-approximator. To establish a hierarchy, our key insight is to consider the common refinement of partitions $\mathcal{P}_{i},\mathcal{P}_{i+1},\ldots,\mathcal{P}_{L}$, which we name $\mathcal{R}_{\geq i}$. The partitions $\mathcal{R}_{\geq i}$ over all $i$ are now hierarchical by construction, and we show that the union of all refinements $\mathcal{R}_{\geq i}$ is a congestion-approximator with good quality.

We emphasize that our conceptual idea of not contracting clusters and looking at common refinements is novel and may have future applications to bottom-up constructions of hierarchical objects, especially for obtaining polylogarithmic approximations, meaning that one cannot lose a multiplicative factor at each level. Given that [14] has popularized bottom-up hierarchical approaches, and that their methods so far can only obtain $n^{o(1)}$-factors due to multiplicative errors across levels, we believe that our ideas are promising for future development in this area.

We are given an undirected, capacitated graph $G=(V,E)$. The graph has $n$ vertices and $m$ edges, and each edge $e\in E$ has capacity $c(e)$ in the range $[1,W]$. For a set $C\subseteq V$, let $\partial C$ denote the set of edges with exactly one endpoint in $C$, and let $\delta C=\sum_{e\in\partial C}c(e)$ denote the total capacity of edges in $\partial C$. For a vertex $v\in V$, let $\deg(v)$ denote the capacitated degree of vertex $v$, which is also equal to $\delta\{v\}$. When the graph $G$ is clear from context, we may drop the subscript $G$. We sometimes write $\partial_{G}C$, $\delta_{G}C$, and $\deg_{G}(v)$ to emphasize that the values are with respect to graph $G$.

For a given edge set $F\subseteq E$, let $\partial_{F}C$, $\delta_{F}C$, and $\deg_{F}(v)$ denote the corresponding values on the subgraph of $G$ with edge set $F$. For a different graph $H$, let $\partial_{H}C$, $\delta_{H}C$, and $\deg_{H}(v)$ denote the corresponding values on graph $H$. We never remove the subscripts $F$ and $H$ to avoid confusion with the original graph $G$.

For a partition $\mathcal{P}$ of the vertex set $V$, we call each part of the partition a cluster. Let $\partial\mathcal{P}$ denote the set of edges whose endpoints belong to different clusters; we can also write $\partial\mathcal{P}=\bigcup_{C\in\mathcal{P}}\partial C$. We also define $\delta\mathcal{P}$ as the total capacity of edges in $\partial\mathcal{P}$.

Let $U$ be an arbitrary set of vertices. For a vector $\mathbf{x}\in\mathbb{R}^{U}$, let $\mathbf{x}(v)$ denote its value on entry $v\in U$. For a vertex subset $S\subseteq U$, define $\mathbf{x}(S)=\sum_{v\in S}\mathbf{x}(v)$, and define $\mathbf{x}|_{S}\in\mathbb{R}^{U}$ as the vector $\mathbf{x}$ restricted to $S$, i.e., $\mathbf{x}|_{S}(v)=\mathbf{x}(v)$ for all $v\in S$ and $\mathbf{x}|_{S}(v)=0$ for all $v\notin S$. For two vectors $\mathbf{s},\mathbf{t}\in\mathbb{R}^{U}$, by $\mathbf{s}\leq\mathbf{t}$ we mean entry-wise inequality, i.e., $\mathbf{s}(v)\leq\mathbf{t}(v)$ for all $v\in U$. For a vector $\mathbf{s}\in\mathbb{R}^{U}$, let $|\mathbf{s}|\in\mathbb{R}^{U}$ be the vector with entry-wise absolute values, i.e., $|\mathbf{s}|(v)=|\mathbf{s}(v)|$.

A demand vector is a vector $\mathbf{b}\in\mathbb{R}^{U}$ whose entries sum to $0$, i.e., $\mathbf{b}(U)=0$. A flow $f$ routes demand $\mathbf{b}$ if each vertex $v\in U$ receives a net flow of $\mathbf{b}(v)$ in the flow $f$. A flow $f$ has congestion $\alpha$ if the amount of flow sent along each (undirected) edge is at most $\alpha$ times the capacity of that edge. Given a flow $f$, a path decomposition of flow $f$ is a collection of directed, capacitated paths such that for any two vertices $u,v\in U$ connected by an edge $e$, the amount of flow that $f$ sends from $u$ to $v$ equals the total capacity of (directed) paths that contain edge $e$ in the direction from $u$ to $v$.

A vertex weighting is a vector $\mathbf{d}\in\mathbb{R}^{U}_{\geq 0}$, i.e., all entries in $\mathbf{d}$ are nonnegative. The vertex weighting $\mathbf{d}\in\mathbb{R}^{U}_{\geq 0}$ mixes in graph $G$ with congestion $\alpha$ if for any demand $\mathbf{b}\in\mathbb{R}^{U}$ satisfying $|\mathbf{b}|\leq\mathbf{d}$, there is a flow routing $\mathbf{b}$ with congestion $\alpha$.¹¹¹¹11There is a close connection between the concept of mixing and expander graphs, though we do not need the definition of expanders in this paper. A collection $\{\mathbf{d}_{1},\mathbf{d}_{2},\ldots,\mathbf{d}_{\ell}\}$ of vertex weightings mixes simultaneously with congestion $\alpha$ if for any demands $\mathbf{b}_{1},\mathbf{b}_{2},\ldots,\mathbf{b}_{\ell}$ with $|\mathbf{b}_{i}|\leq\mathbf{d}_{i}$ for each $i\in[\ell]$, there is a flow routing demand $\mathbf{b}_{1}+\mathbf{b}_{2}+\cdots+\mathbf{b}_{\ell}$ with congestion $\alpha$.

Throughout the paper, we view vectors in $\mathbb{R}^{U}$ and functions from $U$ to $\mathbb{R}$ as interchangeable. In particular, we sometimes treat the degree function $\deg:V\to\mathbb{R}_{\geq 0}$ as a vector $\deg\in\mathbb{R}^{V}_{\geq 0}$. In particular, $\deg$ is a vertex weighting.

In this section, we formally state our congestion-approximator construction and prove its quality guarantee. See Figure 1 for an illustration. The most important distinction is that we define and analyze mixing on vertex weightings, not edges. This simplifies the notation since we can avoid working with the subdivision graph in [33]. For example, in property (2) below, the mixing of the vertex weighting $\mathrm{deg}_{\partial\mathcal{P}_{i}\cup\partial C}|_{C}$ is conceptually equivalent to the mixing of the edges of $\partial\mathcal{P}_{i}$ internal to $C$ together with the boundary edges $\partial C$.

In Section 5, we develop an efficient algorithm to construct partitions $\mathcal{P}_{1},\mathcal{P}_{2},\ldots,\mathcal{P}_{L}$ with $L=O(\log n)$. This algorithm builds the partitions iteratively in the order $\mathcal{P}_{1},\mathcal{P}_{2},\ldots,\mathcal{P}_{L}$. For technical reasons explained in Section 5, we require the following analogue of Theorem 4.1 where $\mathcal{P}_{L}$ is not necessarily the partition $\{V\}$. Note that assumptions (2) and (3) remain unchanged below. The key difference is that $\mathcal{C}$ is no longer a congestion-approximator, but a pseudo-congestion-approximator whose precise guarantee is stated below.

Instead of proving Theorem 4.1 directly, we prove Lemma 4.2 which is needed for the algorithm. Before we do so, we first establish that Lemma 4.2 indeed implies Theorem 4.1.

For the rest of this section, we prove Lemma 4.2. We begin with two helper claims that establish structure on the sets $\mathcal{R}_{\geq i}$.

Let $\mathbf{b}\in\mathbb{R}^{V}$ be a flow demand satisfying $|\mathbf{b}(C)|\leq\delta C$ for all $C\in\mathcal{C}$. We need to construct a demand $\mathbf{b}^{\prime}\in\mathbb{R}^{V}$ satisfying $|\mathbf{b}^{\prime}|\leq L\deg_{\partial\mathcal{P}_{L}}$ and a flow routing demand $\mathbf{b}-\mathbf{b}^{\prime}$ with congestion $5L^{2}\alpha\beta$.

The construction of the flow has $L-1$ iterations. On iteration $i\in[L-1]$, we construct a flow $f_{i}$ and a demand $\mathbf{b}_{i}$ such that

1. 1.

   The flow $f_{i}$ routes demand $\mathbf{b}_{i-1}-\mathbf{b}_{i}$, where we initialize $\mathbf{b}_{0}=\mathbf{b}$ on iteration $i=1$.

2. 2.

   The flow $f_{i}$ has congestion $5L\alpha\beta$.

3. 3.

   For all $C\in\mathcal{R}_{\geq i+1}$, we have $(\mathbf{b}_{i-1}-\mathbf{b}_{i})(C)=0$.

4. 4.

   The demand $\mathbf{b}_{i}$ satisfies $|\mathbf{b}_{i}|\leq(i+1)\deg_{\partial\mathcal{R}_{\geq i+1}}$.

Note for the last level $L-1$, by definition we have $\partial\mathcal{R}_{\geq L}=\partial\mathcal{P}_{L}$. The lemma below shows that properties (1), (2), and (4) alone are sufficient to prove Lemma 4.2 with demand $\mathbf{b}^{\prime}=\mathbf{b}_{L-1}$ and flow $f_{1}+f_{2}+\cdots+f_{L-1}$.

In order to establish the conditions above, we will use the following technical lemma:

Before we prove this lemma, we first establish that it implies properties (1) to (4) above for appropriate $f_{i}$ and $\mathbf{b}_{i}$.

For the rest of this section, we establish Lemma 4.6, the most technical part of the proof. Before we do so, we first establish three technical helper claims.