Faster Weak Expander Decompositions and Approximate Max Flow

Our result builds on a long line of work on efficiently constructing a small collection of cuts, called congestion approximators, which approximately capture the congestion required to route any feasible demand [28, 5, 15, 29, 30, 26, 27, 14, 1, 16]. To construct an $\alpha$-congestion approximator for $\alpha =\text{poly}\log n$, these algorithms required (approximate) max flow as a subroutine. In a breakthrough work, [32] showed that an $\alpha$-congestion approximator could also be used to compute $(1-ϵ)$-approximate max flow. There is a chicken-and-egg problem here as congestion-approximators and approximate max-flow need each other, which [27] resolved using a costly recursion combined with ultra-sparsifiers. Recent work [23] was able to avoid this recursion by building a congestion-approximator bottom-up without requiring an approximate max-flow oracle, which is the focus of our work.

Our expander decomposition algorithm is adapted from the cut-matching game from [19], despite the fact that cut-matching games with better parameters have since been developed. Most notably, the cut-matching game of [25] uses a stronger spectral cut player to save an $O(\log n)$ factor in their expansion guarantees. However, our warm starting analysis relies on a simple property of the potential function used in [19]: if we partition a set $S=S_1\bigsqcup S_2$, then the sum of the induced potentials on $S_1$ and $S_2$ is at most the potential on $S$. The same property is not obviously true of the matrix-based potential function of [25].

Our work also relies essentially on the “nonstop” variant of KRV used in [30, 31] to give an efficient expander decomposition algorithm. Until the recent works of [2, 16], such a nonstop version of [25] was unknown. Given this development, we believe it may be a promising direction to adapt our warm starting analysis to this OSVV-based nonstop cut-matching game. We leave this as an open problem in our work.

All known algorithms for computing expander decompositions in near-linear time rely on the cut-matching game. Our first main technical contribution is a faster algorithm for computing weak expander decompositions. We do this by observing that it is possible to “warm start” our recursive instances of the cut-matching game. Importantly for our application to approximate max flow, our algorithm is robust enough to support general vertex weights and to implement the matching steps using approximate max flow oracles.

We now describe the techniques in more detail. In the standard cut-matching game (on an unweighted graph), we have $T=\mathrm{\Theta }({\log }^{2}n)$ rounds in total. In each round, the cut player finds two disjoint sets $L_A$ and $R_A$. The matching player then tries to route a flow from $L_A$ to $R_A$, implicitly defining a matching between the sets. If at any iteration the matching player fails to route the flow, the cut certifying infeasibility of the flow is a sparse cut, showing that the graph is not an expander. Otherwise, if all matching step flows are feasible, the cut player is defined so that the union of the matchings found in the $T$ iterations is itself an expander. Combined with the fact that the matchings embed into the original graph with low congestion, this proves that $G$ must be an expander.

In the non-stop version of the cut-matching game [30, 31], when the matching player fails to route the flow from $L_A$ to $R_A$, thus finding a sparse cut $S$, the algorithm does not (necessarily) immediately terminate. Instead, the cut-matching game continues on $V\setminus S$. More generally, let $A$ be the current set on which the cut-matching game is being played; when the matching player finds a cut $S$, the algorithm continues on $A\setminus S$. It can be shown that after $T$ iterations, the remaining set $A$ is a near-expander in $G$, meaning that its degree vertex weighting mixes in $G$ (but possibly not $G[A]$) with low congestion.

To convert the non-stop cut-matching game into a weak expander decomposition algorithm, [11] adds an early termination condition: if $\mathrm{vol}(A)\le 99\mathrm{vol}(V)/100$ at any point, the non-stop cut-matching game terminates and recurses on $A$ and $V\setminus A$. Otherwise, if the cut-matching game terminates in certifying that $A$ is a near-expander, we recurse onto $V\setminus A$ if it is non-empty. If $A$ is certified as a near-expander in some iteration, we then know that $\mathrm{vol}(V\setminus A)\le \mathrm{vol}(V)/100$ so the recursive call decreases by a constant factor in size. If we reach the early termination condition, then $\mathrm{vol}(A)\le 99\mathrm{vol}(V)/100$ and we have the additional guarantee that $V\setminus A$ is partitioned by sparse cuts into subsets of at most $2/3$ of the volume each. Hence, the recursive calls also decrease in size by a constant factor in this case. As a result, the recursive depth is at most $O(\log n)$, so we can compute a weak expander decomposition in $O({\log }^{3}n)$ iterations of the cut-matching game.

We give a new weak expander decomposition algorithm which only uses $O({\log }^{2}n)$ iterations of the cut-matching game. Let $A$ again be the current set of vertices. If we find a matching successfully, then we continue the cut-matching game on $A$. Otherwise, we find a sparse cut $S\subseteq A$. In the previous algorithm, we would only continue on $A\setminus S$, delaying continuing on $S$ until reaching the early termination condition or certifying that some subset of $A\setminus S$ is a near-expander in $G$. Our main observation is that we can continue the cut-matching game on both $A\setminus S$ and $S$ simultaneously without a loss in the runtime. This amounts to “warm-starting” on $S$. Slightly more formally, we maintain a partition of $V$ into $k_t$ sets ${𝒜}_t=\{A_1,\mathrm{\dots },A_{k_t}\}$ at each iteration $t$. At the beginning of the algorithm, we set ${𝒜}_0=\{V\}$ and at each iteration $t$, we run the cut-matching game on each $A_i\in {𝒜}_t$ simultaneously. When we find some cut $S_i\subseteq A_i$, we add $S_i$ (if nonempty) and $A_i\setminus S_i$ to ${𝒜}_{t+1}$. After $T$ rounds, we will certify that each component in ${𝒜}_T$ is a near-expander. We remark that warm-starting crucially uses the fact that we are ultimately constructing a weak expander decomposition, not a strong one. Indeed, the matching embeddings from steps prior to restricting to a subgraph (from finding a cut) are not guaranteed to embed into our current subgraph. This is fine for certifying near-expansion but too weak a guarantee for strong expansion.

Importantly for our application to approximate max flow, this algorithm still reveals sufficient structure when implementing the matching steps with an approximate max flow oracle. To this end, we give our algorithm in two steps. The first step is to compute a weak expander decomposition where there can be a small “deleted,” non-expanding portion of the input vertex weighting (Section 5.1). The non-deleted portion is certified to mix simultaneously (i.e., each component expands with respect to the non-deleted portion of the vertex weighting) and there are guaranteed to be few intercluster edges, as usual. Then, in the second step (Section 5.2), we attempt to graft the demand deleted in each cluster back into the cluster, as in [11]. After this step, every expanding cluster will not have any deleted demand, and nearly all demand will belong to an expanding cluster. We state an informal version of our result in Theorem 2.

Importantly for our applications, we actually obtain a stronger simultaneous mixing expansion property instead of (4), but we omit that here for simplicity (see Theorem 15). Also note that, unlike standard weak expander decompositions, our result does not exactly decompose all vertices into near-expanders (i.e., usual decompositions would get ${𝒜}^{\times }=\mathrm{\varnothing }$ or the guarantee of (2) to be $0$). However, this relaxation is critical for obtaining such a result and still suffices for some important applications of weak expander decompositions. Indeed, the relaxation of (2) suffices for our application to constructing congestion-approximators and approximate max flow, as we discuss next.

Recall that a laminar family $𝒞$ of subsets of $V$ forms an $\alpha$-congestion-approximator if for every vertex demand, the minimum ratio over cuts $C\in 𝒞$ between the capacity of the cut and the demand crossing the cut is an $\alpha$-approximation to the optimal congestion of any flow routing the demand. Our goal is to construct $\alpha$-congestion-approximators faster and with smaller $\alpha$. To discuss our improvement over previous work, we restate the informal Theorem 2.1 from [23], which gave a novel approach for constructing congestion-approximators.

The partitions ${𝒫}_i$ described in the theorem essentially form a weak expander hierarchy, where each level is essentially a (boundary-linked) weak expander decomposition. Using the existence of routings guaranteed by (2) and (3), [23] show that a demand respecting the congestion-approximator can be iteratively routed. They then show that this weak expander hierarchy can be constructed using existing tools for constructing expander decompositions [31, 22]. By doing this, they construct a sequence of partition ${𝒫}_1,\mathrm{\dots },{𝒫}_L$ satisfying properties (1), (2), and (3) with parameters $\alpha =O({\log }^{5}n)$ and $\beta =O({\log }^{3}n)$.

Our main observation is that we do not need the full power of a weak expander decomposition at each level in order to show the existence of this routing. If a small constant fraction of the vertices (measured in terms of volume in the subgraph) do not have the expander mixing property, this is still sufficient to show that the congestion-approximator routing exists. Specifically, we relax conditions (2) and (3) on the partitions ${𝒫}_i$ to allow for a small constant fraction of edges to not participate in the routings at level $i$ and be instead be handled at level $i+1$. More formally, we let ${𝒫}_1,\mathrm{\dots },{𝒫}_L$ be partitions of subsets $V_1,\mathrm{\dots },V_L\subseteq V$. We only require the mixing properties (2) and (3) on $V_{i+1}$ for each $i\in [L-1]$, so we should think of ${𝒫}_i$ as a weak expander decomposition of $V_i$. To extend the partitions ${𝒫}_i$ of $V_i$ to a partition ${\overline{𝒫}}_i$ of $V$, we define ${𝒬}_i$ to be the induced partition from the previous level ${\overline{𝒫}}_{i-1}$ on $V\setminus V_i$. That is, we define

Then we can define ${\overline{𝒫}}_i={𝒫}_i\cup {𝒬}_i$. Intuitively, when we only have a partition on $V_i$, we are giving up on routing the demand from the intercluster edges from ${\overline{𝒫}}_{i-1}$ in $V\setminus V_i$ and dealing with it at a higher level. In order to move it to the higher level, we include it in ${\overline{𝒫}}_i$ through the definition of ${𝒬}_i$.

We now state a morally true version of our relaxed conditions for constructing congestion-approximators.

The first advantage of this relaxation is that our algorithm for constructing the partitions ${𝒫}_1,\mathrm{\dots },{𝒫}_L$ is faster. In particular, we can use approximate max flow algorithms to implement the cut-matching game. This may cause some nodes to be “deleted,” as described in the previous subsection, but this is okay for us since we only need expander mixing guarantees on a (large) constant fraction of the vertices for property (2). In contrast, [23] used a fair-cuts algorithm [22] to implement the same step in their paper, which incurred several additional log factors in their runtime.

The second advantage is for obtaining smaller $\beta$. In [23], they prove that the flow from $\partial {𝒫}_{i+1}$ to $\partial {𝒫}_i$ exists using the boundary-linkedness property of the expander decompositions. This approach naturally suffers from $\beta =\mathrm{\Omega }({\log }^{3}n)$ because the flows guaranteed by the expander decomposition have congestion $\mathrm{\Omega }({\log }^{3}n)$. Instead, our approach is to directly attempt to send flow from $\partial {𝒫}_{i+1}$ to $\partial {𝒫}_i$ at each level. Using a max-flow/min-cut algorithm, we will find a (possibly empty) cut and a flow which saturates the cut. If we simply remove the vertices which are cut out, we have that in the remainder of the graph, there is a flow from $\partial {𝒫}_{i+1}$ to $\partial {𝒫}_i$ (since the flow saturates the cut). This gives us the desired $\beta =O(1)$, and also crucially uses our relaxation of properties (2) and (3).

Finally, we note that we obtain a smaller $\alpha =O({\log }^{3}n)$ in our construction. This is because we construct a weak expander decomposition on each level, which we observed is sufficient for the simultaneous mixing guarantees required by property (2). This enables us to avoid the costly trimming step used in [23], and also enables our speedup using warm-starting, which no longer helps for strong expander decompositions.

We apply Sherman’s framework [33] to convert a congestion-approximator into an approximate max flow algorithm. Our approach for constructing a congestion-approximator is to construct a weak expander hierarchy using the cut-matching game. In implementing the cut-matching game, we need to solve flow problems (approximately), and we do this using the previous layers of the hierarchy as a “pseudo”-congestion-approximator. Our (pseudo)-congestion-approximators have quality $\alpha \beta L^2=O({\log }^{5}n)$, giving us an $O(m{\log }^{6}n\log \log n)$ time algorithm for solving the flow problems in the cut-matching game. Our improved weak expander decomposition algorithm takes $T=O({\log }^{2}n)$ rounds to obtain a full weak expander decomposition. Finally, there are $L=O(\log n)$ layers of the hierarchy, totalling $O(m{\log }^{9}n\log \log n)$ runtime.

For two functions $f,g:X\to ℝ$ let $f\le g$ denote that, for all $x\in X$, $f(x)\le g(x)$. We write $\mathrm{supp}(f)$ to denote the subset of $X$ on which $f$ takes nonzero values. For $S\subseteq X$ and $S$ finite, we also write $f(S)$ as shorthand for ${\sum }_{x\in S}f(x)$. We use ${f|}_S$ to mean the restriction of $f$ to $S$. When clear from context, we sometimes abuse notation and use ${f|}_S$ to denote the function $f$ on the same domain but set equal to $0$ outside of $S$. We also use all of the above notation for vectors, interpreting those vectors as functions. We often bold vectors to distinguish them from scalars (e.g., write $𝐝\in {ℝ}^V$).

We consider capacitated (weighted) graphs $G=(V,E,𝐜)$ where $𝐜\in [1,W]\cap \mathbb{Z}$. Unless otherwise specified, we use $n$ to denote the order of $G$ and $m$ to denote its size. Sometimes we write $V_G$ (or $V(G)$), $E_G$ (or $E(G)$), and ${𝐜}_G$ to clarify that they are the parameters of the graph $G$. For $S\subseteq V$, denote the induced subgraph of $G$ as $G[S]$. In other words, $G[S]$ is the subgraph of $G$ formed by retaining exactly vertices in $S$ and edges between vertices in $S$.

Given a partition $𝒜$ of $V$, we write $\partial 𝒜$ to denote the set of intercluster edges in $G$. When $𝒜$ is just a single cut $(S,V\setminus S)$, we sometimes write $\partial S$ instead. We often consider $\partial 𝒜$ as an edge subgraph of $G$. We also use the notation $\delta 𝒜=𝐜(\partial 𝒜)$ and $\delta S=𝐜(\partial S)$ (or $\delta (𝒜)$ and $\delta (S)$) as shorthand denoting the total capacity of intercluster or cut edges. For $u\in V$, we denote the (weighted) degree of $u$ in $G$ as ${\mathrm{deg}}_G(u)={\delta }_G(\{u\})$. We will often also consider ${\mathrm{deg}}_{\partial 𝒜}(u)={\delta }_{\partial 𝒜}(\{u\})$ which treats $\partial 𝒜$ as an edge subgraph of $G$. Finally, throughout we consider vertex weights $𝐝\in {\mathbb{Z}}_{\ge 0}^V$, with the most common weight function being $𝐝={\mathrm{deg}}_G$ or ${\mathrm{deg}}_H$ for $H$ a subgraph of $G$.

A demand is a vector $𝐛\in {ℝ}^V$ whose entries sum to $0$. We say a flow $f:E\to ℝ$ routes a demand $𝐛$ if for each $v\in V$ the net flow at $v$ in $f$ is $𝐛(v)$. We say that $f$ has congestion $\kappa$ if the flow through any edge in $f$ is at most $\kappa$ times its capacity. Given a flow $f$, a path decomposition of $f$ is a collection of weighted paths in $G$ such that, for each $(u,v)\in E$, the flow from $u$ to $v$ in $f$ is the sum of weights of paths containing the edge from $u$ to $v$ in the path decomposition.

Let $G=(V,E,𝐜)$ be a capacitated graph, and let $𝐝\in {ℝ}_{\ge 0}^V$ be a vertex weighting. Let $S\subseteq V$. Then, the conductance of $S$ in $G$ with respect to $𝐝$ is

We say that a cut $S$ is $\varphi$-sparse (in $G$ with respect to $𝐝$) if ${\mathrm{\Phi }}_{G,𝐝}(S)\le \varphi$. We say that $G$ is a $(\varphi ,𝐝)$-expander if, for all $S\subseteq V$, we have ${\mathrm{\Phi }}_{G,𝐝}(S)\ge \varphi$. For $A\subseteq V$, we say that $A$ is $\varphi$-nearly $𝐝$-expanding in $G$ (or $A$ is a $(\varphi ,𝐝)$-near-expander in $G$) if, for all $S\subseteq A$, we have

Note that if $A$ is $\varphi$-nearly $𝐝$-expanding in $G$, then the same holds for all $A^{\prime }\subseteq A$, since the denominators of the relevant expressions only decrease. When $𝐝={\mathrm{deg}}_G$ or $𝐝$ is clear from context we say $G$ is a $\varphi$-expander (respectively, near-expander).

We can also define expansion with respect to flows. We say that a vertex weighting $𝐝\in {ℝ}_{\ge 0}^V$ mixes in $G$ with congestion $\kappa$ if, for all demands $𝐛\in {ℝ}^V$ with $|𝐛|\le 𝐝$, we have that $𝐛$ is routable in $G$ with congestion at most $\kappa$. In fact, $𝐝$ mixes in $G$ with congestion $1/\varphi$ if and only if $G$ is a $(\varphi ,𝐝)$-expander. Note that while ${𝐝|}_A$ mixing in $G$ with congestion $\kappa$ implies that $A$ is a $(\varphi ,𝐝)$-near-expander in $G$, the converse does not hold in general. Flow-based expansion is stronger than cut-based expansion for near-expanders.

Sometimes we require an even stronger notion of expansion with respect to multi-commodity flows. We say that a collection of vertex weights $\{{𝐝}_i:i\in I\}$ mixes simultaneously in $G$ with congestion $\kappa$ if, for all tuples of demands ${({𝐛}_i)}_{i\in I}$ with each ${𝐛}_i\in {ℝ}^V$ satisfying $|{𝐛}_i|\le {𝐝}_i$, there exists a multicommodity flow $𝐅$ with one commodity per demand which routes all ${𝐛}_i$ and has total congestion $\kappa$.

Given a graph $G=(V,E,𝐜)$, a congestion-approximator $𝒞$ of quality $\alpha$ is a family of subsets of $V$ such that, for any demand $𝐛$ satisfying $|𝐛(C)|\le {\delta }_G(C)$ for all $C\in 𝒞$, there is a flow routing demand $𝐛$ with congestion $\alpha$.