Nearly Maximum Flows in Nearly Linear Time

Introduction

In this paper, we introduce a new approach to this problem in undirected graphs. We maintain a flow that may not quite route $b$ exactly, but we also keep track of an upper bound on how much it will cost us in congestion to fix it back up. We will aim to minimize a potential function measuring the current congestion plus an over-estimate on the cost of fixing up the residuals. By not needing to worry about precisely conserving flow at every vertex, we can take large steps in each iteration towards minimizing our potential function. On the other hand, by intentionally over-estimating the cost of fixing up the residuals, in the course of minimizing our potential function we must inevitably fix them up, as it will cost strictly less to do so.

For a graph $G$, let $C$ be the $m\times m$ diagonal matrix containing the edge capacities, and let $B$ be the $n\times m$ divergence matrix, where $(Bf)_{i}$ is the excess at vertex $i$. For a set $S\subseteq V$, we’ll write $b_{S}=\sum_{i\in S}b_{S}$, the total excess in $S$, and $c_{S}=\sum_{e:S\leftrightarrow V\setminus S}c_{e}$, the capacity of the cut $(S,V\setminus S)$ in $G$. A valid demand vector satisfies $b_{V}=0$.

The minimum congestion flow problem for demands $b$, and its dual, the maximum congested cut, are

We refer to the optimum value of these problems as $\mathsf{opt}(b)$. It is well-known that for problem (2), one of the threshold cuts with respect to $v$ achieves $b_{S}/c_{S}\geq b^{\top}v$.

2 Outline

An $\alpha$-congestion-approximator for $G$ is a matrix $R$ such that for any demand vector $b$,

Our main result is that we can use good congestion approximators to quickly find near-optimal flows in a graph. We prove the following theorem in section 2.

For the sake of giving the reader a concrete example of what a congestion-approximator might look like before continuing, we’ll begin with two simple toy examples.

Let $T$ be a maximum weight spanning tree in $G$, and let $R$ be the $n-1\times n$ matrix with a row for each edge in $T$, and

where $(S,V\setminus S)$ is the cut in $G$ induced by removing $e$ from $T$.

Then, $R$ is a $m$-congestion-approximator.

Since $(Rb)_{e}$ is the congestion on the cut in $G$ induced by removing $e$ from $T$, certainly $\mathsf{opt}(b)\geq\|Rb\|_{\infty}$. On the other hand, at least $1/m$ of the capacity of those cuts is contained in $T$, so routing $b$ through $T$ congests $e$ by at most $m|(Rb)_{e}|$. Multiplication by $R$ and $R^{\top}$ can be done in $O(n)$ time via elimination on leaves. ∎

For graphs of large conductance, we can obtain a trivial approximator by simply looking at how much the demand into each vertex congests its total degree.

Let $G$ have conductance $\phi$. Let $R$ be $n\times n$ diagonal matrix with $R_{i,i}=1/\deg(i)$ where $\deg(i)=c_{\{i\}}$. Then, $R$ is a $\phi^{-1}$-congestion-approximator.

Routing $|b_{i}|$ into or out of vertex $i$ certainly must congest one of its edges by at least $|b_{i}|/\deg(i)$, so $\mathsf{opt}(b)\geq\|Rb\|_{\infty}$. On the other hand, the capacity of any cut in $G$ is at least $\phi$ times the total degree of the smaller side. It follows that if no vertex is congested by more than $\beta$, then no cut is congested by more than $\phi^{-1}\beta$. ∎

Congestion Potential

The key to our scheme lies transforming problem (1) to an unconstrained optimization problem, using the congestion-approximator to bound the cost of routing the residual. To that end, we introduce our potential function.

Each iteration requires $O(m)$ time plus a multiplication by $R$ and $R^{\top}$.

The flow $f$ may not quite route the demands we wanted. Fortunately, that will be easy to fix. The extra factor of two in equation (3) means that half of the contribution to the objective value from the residual part is pure slack. On the other hand, if $f$ is nearly optimal, there can’t be too much slack.

Suppose $\|C^{-1}f\|_{\infty}+2\alpha\|R(b-Bf)\|_{\infty}\leq(1+\varepsilon)\mathsf{opt}(b)$. Then, $\|R(b-Bf)\|_{\infty}\leq\varepsilon\|Rb\|_{\infty}$.

Let $f$ meet the assumption. Let $f^{\prime}$ be a routing of $b-Bf$ in $G$ with $\|C^{-1}f^{\prime}\|_{\infty}\leq\alpha\|R(b-Bf)\|_{\infty}$. Then, moving from $f$ to $f+f^{\prime}$ decreases the objective value by atleast $\alpha\|R(b-Bf)\|$. On the other hand, that decrease can’t exceed $\varepsilon\mathsf{opt}(b)$. Since $\mathsf{opt}(b)\leq\alpha\|Rb\|_{\infty}$, the lemma follows. ∎

So while AlmostRoute may not route $b$, our bound for the congestion to route the residual is at most half of our bound to route the original demands. Furthermore, the objective already pays the cost of routing that residual. In fact, it pays it with a factor of two, so we need only route the remaining residual within a factor-two of optimal. That suggests an obvious way to route demands $b$: repeatedly invoke AlmostRoute on the remaining residual, until the congestion required to route it is extremely small compared to the congestion required to route $b$. Then route the final residual in a naive way, such as via a maximal spanning tree. The cost of that final routing will be paid for by the slack in the objective value of the first routing, simply by finding a factor $3/2$-optimal routing for each residual after the first case.

Formalizing the latter argument completes our proof of theorem 1.2. Set $b_{0}\leftarrow b$, and let $(f_{0},S_{0})\leftarrow\mathtt{AlmostRoute}(b_{0},\varepsilon)$. Next for $i=1,\ldots,T$ where $T=\log(2m)$, set $b_{i}\leftarrow b_{i-1}-Bf_{i-1}$ and $(f_{i},S_{i})\leftarrow\mathtt{AlmostRoute}(b_{i},1/2)$ (we don’t actually need any $S_{i}$ after $S_{0})$. Finally, let $b_{T+1}=b_{t}-Bf_{t}$, and let $f_{T+1}$ be a flow routing $b_{T+1}$ in a maximal spanning tree of $G$. Output $f_{1}+\cdots+f_{T+1}$ and $S_{0}$. Observe that theorem 2.1 yields

Beginning with the former inequality and repeatedly applying the latter yields,

On the other hand, by choice of $T$, we have

We approximate $\|\cdot\|_{\infty}$ using the symmetric softmax function.

We make use of some elementary facts about $\operatorname{lmax}$.

We will approximate problem (3) with the potential function,

Since equation (7) approximates equation (3) to within an additive $\theta(\log n)$, we will be concerned with minimizing $\phi(f)$ after scaling $f,b$ so $\phi(f)=\theta(\varepsilon^{-1}\log n)$.

$\mathtt{AlmostRoute}(b,\varepsilon)$: • Initialize $f=0$, scale $b$ so $2\alpha\|Rb\|_{\infty}=16\varepsilon^{-1}\log(n)$. • Repeat: – While $\phi(f)<16\varepsilon^{-1}\log(n)$, scale $f$ and $b$ up by $17/16$. – Set $\delta\leftarrow\|C\nabla\phi(f)\|_{1}$. – If $\delta\geq\varepsilon/4$, set $f_{e}\leftarrow f_{e}-\frac{\delta}{1+4\alpha^{2}}\operatorname{sgn}(\nabla\phi(f)_{e})c_{e}$ – Otherwise, terminate and output $f$ together with the potentials induced by $\nabla\phi(f)$(see below), after undoing any scaling.

Each step requires computing $\nabla\phi(f)$, which requires $O(m)$ time plus a multiplication by $R$ and a multiplication by $R^{\top}$. Further, the partial derivative of the residual part for a particular edge is equal to a potential difference between the endpoints of that edge. When $\phi(f)$ is nearly-optimal, those potentials yield a good dual solution for our original problem.

When $\mathtt{AlmostRoute}$ terminates, we have a flow $f$ and potentials $v$ with,

Set $x_{1}=C^{-1}f$, $x_{2}=2\alpha R(b-Bf)$, and $p_{i}=\nabla\operatorname{lmax}(x_{i})$. Set $v=R^{\top}p_{2}$ to be our potentials. Observe that $\nabla\phi(f)=C^{-1}p_{1}-2\alpha B^{\top}v$. First, equation (4) yields

By equation (5), using the fact that $C$ and $R$ have at most $n^{2}/2$ rows and $\phi(f)\geq 16\varepsilon^{-1}\log n$,

Altogether, using the fact that $\delta<\varepsilon/4$ at termination, we have

Observing that $\phi(f)$ overestimates $\|C^{-1}f\|_{\infty}+2\alpha\|R(b-Bf)\|_{\infty}$ completes the proof. ∎

Let us call the iterations between each scaling a phase. Since $\|Rb\|_{\infty}$ gives us the correct scale to within factor $\alpha$, we will scale at most $O(\log\alpha)$ times.

Let $h_{e}=-\frac{\delta}{1+4\alpha^{2}}\operatorname{sgn}(\nabla_{f}\phi(f)_{e})c_{e}$ be our step. Then, equation (6), together with the fact that $\|RBC\|_{\infty\to\infty}\leq 1$ for a congestion-approximator $R$ yields,

Since we raised $\phi(f)$ by at most $\varepsilon^{-1}\log n$ when scaling, and each step drops $\phi(f)$ by at least $\Omega(\varepsilon^{2}\alpha^{-2})$, there can be at most $O(\alpha^{2}\varepsilon^{-3}\log n)$ steps between phases. ∎

Computing Congestion-Approximators

In this section we prove theorem 1.5, using a construction of Madry, itself based on a construction of Spielman and Teng.

A $j$-tree is a graph formed by the union of a forest with $j$ components, together with a graph $H$ on $j$ vertices, one from each component. The graph $H$ is called the core.

Each $G_{i}$ is a $O(m\log m/t)$-tree, with a core containing at most $m$ edges.

We briefly remark that while the statement of theorem 3.2 in contains an additional logarithmic dependence on the capacity-ratio of $G$, that dependence is easily eliminated. We elaborate further in appendix A. Our construction will simply apply theorem 3.2 recursively, sparsifying the core on each iteration. To accomplish that, we use an algorithm of Benczúr and Karger.

Further, the edges of $G^{\prime}$ are scaled versions of a subset of edges in $G$, with no edge scaled by more than $(1+\varepsilon)m/m^{\prime}$.

We now present the algorithm for computing the data structure representing a congestion-approximator. The algorithm $\mathtt{ComputeTrees}$ assumes its input is sparse; our top-level data-structure is constructed by invoking $\mathtt{ComputeTrees}(\mathtt{Sparsify}(G,1),n^{1/k})$, where $k$ is the parameter of theorem 1.5.

$\mathtt{ComputeTrees}(G,t)$: • If $n=1$, return. • Using theorem 3.2, compute distribution $(\lambda_{i},G_{i})_{i}^{t^{\prime}}$ of $\max(1,n/t)$-trees. • Pick the $t$ graphs of largest $\lambda_{i}$, throw away the rest, and scale the kept $\lambda_{i}$ to sum to $1$. • For $i=1,\ldots,t$: – $H_{i}^{\prime}\leftarrow\mathtt{Sparsify}(H_{i},1)$, where $H_{i}$ is the core of $G_{i}$ – $L_{i}\leftarrow\mathtt{ComputeTrees}(H_{i}^{\prime},t)$ • Return the list $L=(\lambda_{i},F_{i},L_{i})_{i=1}^{t}$ where $F_{i}$ is the forest of $G_{i}$.

The analysis of $\mathtt{ComputeTrees}$ correctness will make use of another algorithm for sampling trees. The $\mathtt{SampleTree}$ procedure is only used for analysis, and is not part of our flow algorithm.

$\mathtt{SampleTree}(L=(\lambda_{i},F_{i},T_{i})_{i}^{t})$: • Pick $i$ with probability $\lambda_{i}$. • Output $F_{i}+\mathtt{SampleTree}(T_{i})$

By induction on $n$. For $n=1$ the claim is vacuous, so suppose $n=t^{k+1}$. Since $G$ has $O(n\log n)$ edges, the distribution output by theorem 3.2 will have $O(t\log^{2}n)$ entries. We have $H_{i}^{\prime}\geq H_{i}$ and $H_{i}+F_{i}\geq G$. Furthermore, the inductive hypothesis implies that every tree $T_{i}$ in $\mathtt{SampleTree}(L_{i})$ dominates $H_{i}^{\prime}$. Then,

Sparsifying the distribution from $O(t\log^{2}n)$ to $t$ scales $\lambda_{i}$ by at most $O(\log^{2}n)$, so that $\sum_{i=1}^{t}\lambda_{i}G_{i}$ is routable in $G$ with congestion at most $\log^{2}n$ larger than the original distribution. Since $H_{i}^{\prime}\leq 2H_{i}$, by the multicommodity max-flow/min-cut theorem $H_{i}^{\prime}$ is routable in $H_{i}$ with congestion $O(\log n)$. By the inductive hypothesis, $\mathbf{E}[\mathtt{SampleTree}(L_{i})]$ is routable in $H_{i}^{\prime}$ with congestion $\log^{O(k)}(n)$. It follows then that $\mathbf{E}[\mathtt{SampleTree}(L)]$ is routable in $G$ with congestion at most $\log^{O(k+1)}(n)$.

Since the capacity of each tree-edge dominates the capacity of the corresponding cut in $G$, $\mathsf{opt}(b)\geq\|Rb\|_{\infty}$. On the other hand, $b$ can be routed in every tree with congestion $\|Rb\|_{\infty}$. By routing a $\mathbf{Pr}[T]$ fraction of the flow through tree $T$, we route $b$ in $\mathbf{E}[\mathtt{SampleTree}(L)]$ with congestion $\|Rb\|_{\infty}$. But then $b$ can be routed in $G$ while congesting by at most an $\alpha$ factor larger.

The total number of edges in $R$ satisfies the recurrence $E(n)\leq nt+tE(n/t)$ as each edge is either in one of the $t$ toplevel forests, or in one of the $t$ subgraphs. ∎

Having constructed our representation of $R$, it remains only to show how to multiply by $R$ and $R^{\top}$. We use the following lemmas as subroutines, which are simple applications of leaf-elimination on trees.

There is an algorithm $\mathtt{TreeFlow}$ that, given a tree $T$ and a demand vector $b$, takes $O(n)$ time and outputs for each tree edge, the flow along that edge when routing $b$ in $T$.

There is an algorithm $\mathtt{TreePotential}$ that, given a tree $T$ annotated with a price $p_{e}$ for each edge, takes $O(n)$ time and outputs a vector of vertex potentials $v$ such that, for any $i,j$, the sum of the prices on the path from $j$ to $i$ in $T$ is $v_{i}-v_{j}$.

We begin with computing $R$. We take as input the demand vector $b$, and then annotate each forest edge $e$ with the congestion $r_{e}$ induced by routing $b$ through a tree containing $e$.

$\mathtt{Compute}R(b,L=(\lambda_{i},F_{i},T_{i})_{i}^{t})$: • For $i=1,\ldots,t$: – Let $T$ be the tree formed by taking $F_{i}$, adding a new vertex $s$, and an edge from $s$ to each core-vertex of $F_{i}$. Augment $b$ with demand zero to the new vertex. – $f\leftarrow\mathtt{TreeFlow}(b,T)$. – Set $r_{e}\leftarrow f_{e}/c_{e}$ for each forest edge in $F_{i}$. – Set $b^{\prime}$ to a vector indexed by core-vertices, with $b^{\prime}_{j}$ equal to the flow on the edge from $s$ to core-vertex $j$. – $\mathtt{ComputeR}(b^{\prime},T_{i})$.

Let $L=(\lambda_{i},F_{i},T_{i})_{i}^{t}$. We argue by induction on the depth of recursion. Fix a level and index $i$. Observe that the cut in $G$ induced by cutting a forest edge is the same regardless of what tree $T$ lies on the core: it is the cut that separates the part of $F_{i}$ not containing the core from the rest of the vertices. It follows that we may place any tree on the core vertices, invoke $\mathtt{TreeFlow}$, and obtain the flow on each forest edge. Next, for each component $S$ of $F_{i}$, the total excess $b_{S}$ must enter $S$ via the core vertex. It follows that in a flow routing $b$ on $F_{i}+T^{\prime}$, for any tree $T^{\prime}$, the restriction of that flow to $T^{\prime}$ must have excess $b_{S}$ on the core vertex of $S$, so it suffices to find a flow in the core with demands $b^{\prime}_{j}=b_{S_{j}}$. But routing $b$ in $F_{i}+T$ will place exactly $b_{S_{j}}$ units of flow on the edge from $s$ to core-vertex $j$.

To compute $R^{\top}$, we assume each forest edge $e$ has been annotated with a price $p_{e}$ that must be paid by any flow per unit of congestion on that edge, and output potentials $v$ such that $v_{i}-v_{j}$ is the total price to be paid for routing a unit of flow from $j$ to $i$.

$\mathtt{Compute}R^{\top}(L=(\lambda_{i},F_{i},T_{i})_{i}^{t})$: • $v\leftarrow 0$ • For $i=1,\ldots,t$: – $v^{\prime}\leftarrow\mathtt{Compute}R^{\top}(T_{i})$. – Let $T$ be the tree formed by taking $F_{i}$, adding a vertex $s$, and an edge from $s$ to each core-vertex of $F_{i}$. Set $q_{e}=p_{e}/c_{e}$ for each forest edge, and $q_{e}=v^{\prime}_{j}$ for edge $e$ from $s$ to core-vertex $j$. – $v^{\prime\prime}\leftarrow\mathtt{TreePotential}(T,q)$ – Add $v^{\prime\prime}$ to $v$ after removing the entry for $s$. • Return $v$

Given edges annotated with per-congestion prices, the procedure $\mathtt{Compute}R^{\top}(L)$ correctly returns potentials $v$ such that $v_{k}-v_{j}$ is the cost per unit of flow from vertex $j$ to $k$.

Let $L=(\lambda_{i},F_{i},T_{i})_{i}^{t}$. We argue by induction on the depth of recursion. Fix a level; a flow must pay its toll to each $G_{i}$, so the resulting potential equals the sum of the potentials for each $i$. Fix an index $i$. A unit of flow from $j$ to $k$ is first routed from $j$ to the core-vertex of the component of $F_{i}$ containing $j$, then to the core-vertex of the component containing $k$, and then finally to $k$. By induction, we assume that $v^{\prime}$ yields potentials that give the per-unit costs of routing between core-vertices. Placing a star on the core with the edge from $s$ to core-vertex $j$ having per-unit cost $v^{\prime}_{j}$ preserves those costs. If $p_{e}$ is the price of an edge per unit of congestion, then $q_{e}=p_{e}/c_{e}$ is the price of an edge per unit of flow. It follows that the total toll paid is the same as the toll paid in $T$; thus, the potentials output by $\mathtt{TreePotential}(T,q)$ are correct.

Final Remarks

We remark that there are many other ways to obtain good congestion approximators. The oblivious routing schemes of require polynomial time to compute, but, once computed, give us a single tree whose single-edge cuts yield a $\log(n)^{O(1)}$-congestion approximator. Furthermore, we only need the actual tree, and not the routings of the tree back in the original graph. If such a single tree could be computed in nearly-linear time, it would make an ideal candidate for use in our algorithm.

There have been substantial simplifications to Spielman and Teng’s original algorithm (see ). It may be possible to use some of those techniques to further simplify our algorithm.

References

Appendix A Fixing Theorem 3.2

The proof of theorem 3.2 maintains a length function $l(e)$ for each edge, and repeatedly invokes an algorithm $\mathtt{SmallStretchTree}$ that returns a spanning tree $T$ on $G$ with,

where $l_{T}(e)$ is the length of the path between $e$’s endpoints in the tree. Without loss of generality, by scaling, we assume $\sum_{e}l(e)c(e)=m$. Let $\chi(e,e^{\prime})=1$ if $e^{\prime}$ is a tree edge that lies on the path in $T$ containing $e$. Then,

where $c_{T}(e^{\prime})$ is the total capacity of edges routed through $e^{\prime}$ in $T$.