An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations

Introduction

Given a graph $G=(V,E)$ in which each edge $e\in E$ is assigned a nonnegative capacity $\vec{\mu}_{e}$, the maximum $s$-$t$ flow problem asks us to find a flow $\vec{f}$ that routes as much flow as possible from a source vertex $s$ to a sink vertex $t$ while sending at most $\vec{\mu}_{e}$ units of flow over each edge $e$. Its generalization, the maximum concurrent multicommodity flow problem, supplies $k$ source-sink pairs $(s_{i},t_{i})$ and asks for the maximum $\alpha$ such that we may simultaneously route $\alpha$ units of flow between each source-sink pair. That is, it asks us to find flows $\vec{f}_{1},\dots,\vec{f}_{k}$ (which we think of as corresponding to $k$ different commodities) such that $\vec{f}_{i}$ sends $\alpha$ units of flow from $s_{i}$ to $t_{i}$, and $\sum_{i}|\vec{f}_{i}(e)|\leq\vec{\mu}_{e}$ for all $e\in E$.

These problems lie at the core of graph algorithms and combinatorial optimization, and they have been extensively studied over the past 60 years . They have found a wide range of theoretical and practical applications , and they are widely used as key subroutines in other algorithms (see ).

We believe that both our general framework and several of the pieces necessary for its present instantiation are of independent interest, and we hope that they will find other applications. These include:

a non-Euclidean generalization of gradient descent, bounds on its performance, and a way to use this to reduce approximate maximum flow and maximum concurrent flow to oblivious routing;

the definition and efficient construction of flow sparsifiers; and

the construction of a new oblivious routing scheme that can be implemented extremely efficiently.

We have aimed to make our algorithm fairly modular and have thus occasionally worked in slightly more generality than is strictly necessary for the problem at hand. This has slightly increased the length of the exposition, but we believe that it clarifies the high-level structure of the argument, and it will hopefully facilitate the application of these tools in other settings.

For the first several decades of its study, the fastest algorithms for the maximum flow problem were essentially all deterministic algorithms based on combinatorial techniques, such as augmenting paths, blocking flows, preflows, and the push-relabel method. These culminated in the work of Goldberg and Rao , which computes exact maximum flows in time $O(\min(n^{2/3},m^{1/2})\log(n^{2}/m)\log U)$ on graphs with edge weights in $\{0,\dots,U\}$. We refer the reader to for a survey of these results.

More recently, a collection of new techniques based on randomization, spectral graph theory and numerical linear algebra, graph decompositions and embeddings, and iterative methods for convex optimization have emerged. These have allowed researchers to provide better provable algorithms for a wide range of flow and cut problems, particularly when one aims to obtain approximately optimal solutions on undirected graphs.

Our algorithm draws extensively on the intellectual heritage established by these works. In this section, we will briefly review some of the previous advances that inform our algorithm. We do not give a comprehensive review of the literature, but instead aim to provide a high-level view of the main tools that motivated the present work, along with the limitations of these tools that had to be overcome. For simplicity of exposition, we primarily focus on the maximum $s$-$t$ flow problem for the remainder of the introduction.

In , Benczur and Karger showed how to efficiently approximate any graph $G$ with a sparse graph $G^{\prime}$ on the same vertex set. To do this, they compute a carefully chosen probability $p_{e}$ for each $e\in E$, sample each edge $e$ with probability $p_{e}$, and include $e$ in $G^{\prime}$ with its weight increased by a factor of $1/p_{e}$ if it is sampled. Using this, they obtain, in nearly linear time, a graph $G^{\prime}$ with $O(n\log n/\varepsilon^{2})$ edges such that the total weight of the edges crossing any cut in $G^{\prime}$ is within a multiplicative factor of $1\pm\varepsilon$ of the weight crossing the corresponding cut in $G$. In particular, the Max-Flow Min-Cut Theorem implies that the value of the maximum flow on $G^{\prime}$ is within a factor of $1\pm\varepsilon$ of that of $G$.

This is an extremely effective tool for approximately solving cut problems on a dense graph $G$, since one can simply solve the corresponding problem on the sparsified graph $G^{\prime}$. However, while this means that one can approximately compute the value of the maximum $s$-$t$ flow on $G$ by solving the problem on $G^{\prime}$, it is not known how to use the maximum $s$-$t$ flow on $G^{\prime}$ to obtain an actual approximately maximum flow on $G$. Intuitively, this is because the weights of edges included in $G^{\prime}$ are larger than they were in $G$, and the sampling argument does not provide any guidance about how to route flows over these edges in the original graph $G$.

In their breakthrough paper , Spielman and Teng showed how to solve Laplacian systems in nearly-linear time. (This was later sped up and simplified by Koutis, Miller, and Peng and Kelner, Orecchia, Sidford, and Zhu .) Their algorithm worked by showing how to approximate the Laplacian $\mathbf{\mathcal{L}}_{G}$ of a graph $G$ with the Laplacian $\mathbf{\mathcal{L}}_{H}$ of a much simpler graph $H$ such that one could use the ability to solve linear systems in $\mathbf{\mathcal{L}}_{H}$ to accelerate the solution of a linear system in $\mathbf{\mathcal{L}}_{G}$. They then applied this recursively to solve the linear systems in $\mathbf{\mathcal{L}}_{H}$. In addition to providing the electrical flow primitive used by the algorithms described above, the structure of their recursive sequence of graph simplifications provides the motivating framework for much of the technical content of our oblivious routing construction.

In an oblivious routing scheme, one specifies a linear operator taking any demand vector to a flow routing these demands over the edges of $G$. Given a collection of demand vectors, one can produce a multicommodity flow meeting these demands by routing each demand vector using this pre-specified operator, independently of the others. The competitive ratio of such an operator is the worst possible ratio between the congestion incurred by a set of demands in this scheme and the congestion of the best multicommodity flow routing these demands.

In , Räcke showed how to construct an oblivious routing scheme with a competitive ratio of $O(\log n)$. His construction worked by providing a probability distribution over trees $T_{i}$ such that $G$ embeds into each $T_{i}$ with congestion at most 1, and such that the corresponding convex combination of trees embeds into $G$ with congestion $O(\log n)$. In a sense, one can view this as showing how to approximate $G$ by a probability distribution over trees. Using this, he was able to show how to obtain polylogarithmic approximations for a variety of cut and flow problems, given only the ability to solve these problems on trees.

We note that such an oblivious routing scheme clearly yields a logarithmic approximation to the maximum flow and maximum concurrent multicommodity flow problems. However, Räcke’s construction took time substantially superlinear time, making it too slow to be useful for computing approximately maximum flows. Furthermore, it only gives a logarithmic approximation, and it is not clear how to use this a small number of times to reduce the error to a multiplicative $\varepsilon$.

In a later paper , Madry applied a recursive technique similar to the one employed by Spielman and Teng in their Laplacian solver to accelerate many of the applications of Räcke’s construction at the cost of a worse approximation ratio. Using this, he obtained almost-linear-time polylogarithmic approximation algorithms for a wide variety of cut problems.

Unfortunately, his algorithm made extensive use of sparsification, which, for the previously mentioned reasons, made it unable to solve the corresponding flow problems. This meant that, while it could use flow-cut duality to find a polylogarithmic approximation of the value of a maximum flow, it could not construct a corresponding flow or repeatedly apply such a procedure a small number of times to decrease the error to a multiplicative $\varepsilon$.

In simultaneous, independent work , Jonah Sherman used somewhat different techniques to find another almost-linear-time algorithm for the (single-commodity) maximum flow problem. His approach is essentially dual to ours: Our algorithm maintains a flow that routes the given demands throughout its execution and iteratively works to improve its congestion. Our main technical tools thus consist of efficient methods for finding ways to route flow in the graph while maintaining flow conservation. Sherman, on the other hand, maintains a flow that does not route the given demands, along with a bound on the congestion required to route the excess flow at the vertices. He then uses this to iteratively work towards achieving flow conservation. (In a sense, our algorithm is more in the spirit of augmenting paths, whereas his is more like preflow-push.) As such, his main technical tools are efficient methods for producing dual objects that give congestion bounds. Objects meeting many of his requirements were given in the work of Madry (whereas there were no previous constructions of flow-based analogues, requiring us to start from scratch); leveraging these allows him to avoid some of the technical complexity required by our approach. We believe that these paper nicely complement each other, and we enthusiastically refer the reader to Sherman’s paper.

2. Our Approach

In this section, we give a high-level description of how we overcome the obstacles described in the previous section. For simplicity, we suppose for the remainder of this introduction that all edges have capacity 1.

The problem is thus to send as many units of flow as possible from $s$ to $t$ without sending more than one unit over any edge. It will be more convenient for us to work with an equivalent congestion minimization problem, where we try to find the unit $s$-$t$ flow $\vec{f}$ (i.e., a flow sending one unit from $s$ to $t$) that minimizes $\|f\|_{\infty}=\max_{e}|\vec{f}_{e}|$. If we begin with some initial unit $s$-$t$ flow $\vec{f}_{0}$, the goal will be thus be to find the circulation $\vec{c}$ to add to $\vec{f}_{0}$ that minimizes $\|\vec{f}_{0}+\vec{c}\|_{\infty}$.

We give an iterative algorithm to approximately find such a $\vec{c}$. There are $2^{O(\sqrt{\log n\log\log n})}/\varepsilon^{2}$ iterations, each of which adds a circulation to the present flow and runs in $m\cdot 2^{O(\sqrt{\log n\log\log n})}$ time. Constructing this scheme consists of two main parts: an iterative scheme that reduces the problem to the construction of a projection matrix with certain properties; and the construction of such an operator.

The simplest way to improve the flow would be to just perform gradient descent on the maximum congestion of an edge. There are two problems with this:

The first problem is that gradient descent depends on having a smoothly varying gradient, but the infinity norm is very far from smooth. This is easily remedied by a standard technique: we replace the infinity norm with a smoother “soft max” function. Doing this would lead to an update that would be a linear projection onto the space of circulations. This could be computed using an electrical flow, and the resulting algorithm would be very similar to the unaccelerated gradient descent algorithm in .

To apply this to our problem, we write flows meeting our demands as $\vec{f}_{0}+\vec{c}$, as described above. We then need a parametrization of the space of circulations so that the objective function (after being smoothed using soft max) has a good bound on its Lipschitz constant. Similarly to what occurs in , this comes down to finding a good linear representation of the space of circulations, which we show amounts in the present setting to finding a matrix that projects into the space of circulations while meetings certain norm bounds.

Constructing a projection matrix

This reduces our problem to the construction of such a projection matrix. A simple calculation shows that any linear oblivious routing scheme $A$ with a good competitive ratio gives rise to a projection matrix with the desired properties, and thus leads to an iterative algorithm that converges in a small number of iterations. Each of these iterations performs a matrix-vector multiplication with both $\mathbf{A}$ and $\mathbf{A}^{T}$.

However, the computation involved in existing oblivious routing schemes is not fast enough to be used in this setting. Our task thus becomes constructing an oblivious routing scheme that we can compute and work with very efficiently. We do this with a recursive construction that reduces oblivious routing in a graph to oblivious routing in various successively simpler graphs.

To this end, we show that if $G$ can be embedded with low congestion into $H$ (existentially), and $H$ can be embedded with low congestion into $G$ efficiently, one can use an oblivious routing on $H$ to obtain an oblivious routing on $G$. The crucial difference between the simplification operations we perform here and those in previous papers (e.g., in the work of Benczur-Karger and Madry ) is that ours are accompanied by such embeddings, which enables us to transfer flows from the simpler graphs to the more complicated ones.

We construct our routing scheme by recursively composing two types of reductions, each of which we show how to implement without incurring a large increase in the competitive ratio:

Vertex elimination This shows how to efficiently reduce oblivious routing on a graph $G=(V,E)$ to routing on $t$ graphs with roughly $\widetilde{O}(|E|/t)$ vertices. To do this, we show how to efficiently embed $G$ into $t$ simpler graphs, each consisting of a tree plus a subgraph supported on roughly $\widetilde{O}{(|E|/t)}$ vertices. This follows easily from a careful reading of Madry’s paper . We then show that routing on such a graph can be reduced to routing on a graph with at most $\widetilde{O}{(|E|/t)}$ vertices by collapsing paths and eliminating leaves.

Flow sparsification This allows us to efficiently reduce oblivious routing on an arbitrary graph to oblivious routing on a graph with $\widetilde{O}(|V|)$ edges, which we call a flow sparsifier.

To construct flow sparsifiers, we use local partitioning to decompose the graph into well-connected clusters that contain many of the original edges. (These clusters are not quite expanders, but they are contained in graphs with good expansion in a manner that is sufficient for our purposes.) We then sparsify these clusters using standard techniques and then show that we can embed the sparse graph back into the original graph using electrical flows. If the graph was originally dense, this results in a sparser graph, and we can recurse on the result. While the implementation of these steps is somewhat different, the outline of this construction parallels Spielman and Teng’s approach to the construction of spectral sparsifiers .

Combining these two reductions recursively yields an efficient oblivious routing scheme, and thus an algorithm for the maximum flow problem.

Finally, we show that the same framework can be applied to the maximum concurrent multicommodity flow problem. While the norm and regularization change, the structure of the argument and the construction of the oblivious routing scheme go through without requiring substantial modification.

Preliminaries

Cuts: For any vertex subset $S\subseteq V$ we denote the cut induced by $S$ by the edge subset

and we denote the conductance of a graph by

We call a set of flows $\{\vec{f}_{i}\}$ that meet demands $\{\vec{\chi}_{i}\}$, i.e. $\forall i,\mathbf{B}^{T}\vec{f}_{i}=\vec{\chi}_{i}$, a multicommodity flow meeting the demands.

Running Time: For matrix $\mathbf{A},$ we let $\mathcal{T}\left(\mathbf{A}\right)$ denote the maximum amount of time needed to apply $\mathbf{A}$ or $\mathbf{A}^{T}$ to a vector.

Solving Max-Flow Using a Circulation Projection

Fact 53 shows that this definition indeed yields that \big{\langle}\vec{y},\vec{x}\big{\rangle}\leq\|\vec{y}\|^{*}\|\vec{x}\|. Next, we define the fastest increasing direction ${x}^{\#}$, which is an arbitrary point satisfying the following

In the appendix, we provide some facts about $\|\cdot\|^{*}$ and ${\vec{x}}^{\#}$ that we will use in this section. Using the notations defined, the gradient descent method simply produces a sequence of $\vec{x}_{k}$ such that

where $t_{k}$ is some chosen step size for iteration $k$. To determine what these step sizes should be we need some information about the smoothness of the function, in particular, the magnitude of the second order term in (1). The natural notion of smoothness for gradient descent is the Lipschitz constant of the gradient of $f$, that is the smallest constant $L$ such that

In the appendix we provide an equivalent definition and a way to compute $L$, which is useful later.

We assume that $X^{*}$ is non-empty. Now, we are ready to estimate the convergence rate of the gradient descent method.

By the Lipschitz continuity of the gradient of $f$ and Lemma 54 we have

Furthermore, by the convexity of $f$, we know that

Using this and the fact that $f(\vec{x}_{k})$ decreases monotonically with $k$, we get

Furthermore, since $\phi_{k}\geq\phi_{k+1}$, we have

Now, note that since $\bigtriangledown f(\vec{x}^{*})=0$, we have that

So, we have that $\phi_{0}\leq\frac{L}{2}R^{2}$ and putting this all together yields that

2. Maximum Flow Formulation

Equivalently, we want to compute a minimum congestion flow

where we call $\|\mathbf{U}^{-1}\vec{f}\|_{\infty}$ the congestion of $\vec{f}$.

where the output flow is $\vec{f}=\vec{f}_{0}+\vec{c}$. Although the gradient descent method is applicable to constrained optimization problems and has a similar convergence guarantee, the sub-problem involved in each iteration is a constrained optimization problem, which is quite complicated in this case. Since the domain is a linear subspace, the constraints can be avoided by projecting the variables onto this subspace.

Formally, we define a circulation projection matrix as follows.

Applying gradient descent on this problem is similar to applying projected gradient method on the original problem. But, instead of using the orthogonal projection that is not suitable for $\|\cdot\|_{\infty}$, we will pick a better projection matrix.

3. An Approximate Maximum Flow Algorithm

Now we consider the following regularized optimization problem

For the rest of this section, we consider solving this optimization problem using gradient descent under $\|\cdot\|_{\infty}$.

First, we bound the Lipschitz constant of the gradient of $g_{t}$.

The gradient of $g_{t}$ is Lipschitz continuous with Lipschitz constant $L=\frac{\|\mathbf{P}\|_{\infty}^{2}}{t}$

Seting $\vec{x}\leftarrow\vec{\alpha_{0}}+\mathbf{P}\vec{x}$ and $\vec{y}\leftarrow\vec{\alpha_{0}}+\mathbf{P}\vec{y}$, we have

Hence, the result follows from Lemma 54.∎

Now, we apply gradient descent to find an approximate max flow as follows.

We remark that the initial flow can be obtained by BFS and the OPT value can be approximted using binary search. In Section 7, we will give an algorithm with better dependence on $\|\mathbf{P}\|$.

Let $\widetilde{\mathbf{P}}$ be a cycle projection matrix, let $\mathbf{\mathbf{P}}=\mathbf{\mathbf{U}}^{-1}\widetilde{\mathbf{P}}\mathbf{U}$, and let $\varepsilon<1$. MaxFlow outputs an $(1-\varepsilon)$-approximate maximum flow in time

First, we bound $\|\vec{\alpha_{0}}\|_{\infty}$. Let $\vec{x}^{*}$ be a minimizer of $\min_{\vec{x}}\|\mathbf{U}^{-1}\vec{f}_{0}+\mathbf{P}\vec{x}\|_{\infty}$ such that $\mathbf{P}\vec{x}^{*}=\vec{x}^{*}$. Then, we have

Second, we bound $R$ in Theorem 1. Note that

Hence, the condition $g_{t}(\vec{x})\leq g_{t}(\vec{x}_{0})$ implies that

For any $\vec{y}\in X^{*}$ let $\vec{c}=\vec{x}-\mathbf{P}\vec{x}+\vec{y}$ and note that $\mathbf{P}\vec{c}=\mathbf{P}\vec{y}$ and therefore $\vec{c}\in X^{*}$. Using these facts, we can bound $R$ as follows

From Lemma 3, we know that the Lipschitz constant of $\bigtriangledown g_{t}$ is $\|\mathbf{P}\|_{\infty}^{2}/t$. Hence, Theorem 1 shows that

Using $t=\varepsilon\text{OPT}/2\ln(2m)$ and $k=300\|\mathbf{P}\|_{\infty}^{4}\ln(2m)/\varepsilon^{2}$, we have

Therefore, $\vec{\alpha_{0}}+\mathbf{P}\vec{x}_{k}$ is an $(1-\varepsilon)$ approximate maximum flow.

Now, we estimate the running time. In each step $5$, we are required to compute ${(\bigtriangledown g(\vec{x}_{k}))}^{\#}$. The gradient

In $\|\cdot\|_{\infty}$, the $\#$ operator is given by the explicit formula

It is easy to see that for all $e\in E$, $||{\vec{x}}^{\#}||_{\infty}=\left|\left({\vec{x}}^{\#}\right)_{e}\right|$ . In particular, we have

Fact 52 shows that $||{\vec{x}}^{\#}||_{\infty}=\|\vec{x}\|_{1}$ and the result follows.∎

4. Properties of soft max

For notational simplicity, for all $\vec{x}$ where this vector is clear from context, we define $\vec{c}$ and $\vec{s}$ as follows

where the letters are chosen due to the very close resemblance to hyperbolic sine and hyperbolic cosine.

Thus, the first part follows from Lemma 55. For the later part, we have

Oblivious Routing

In the previous sections, we saw how a circulation projection matrix can be used to solve max flow. In the next few sections, we show how to efficiently construct a circulation projection matrix to obtain an almost linear time algorithm for solving max flow.

Our proof focuses on the notion of (linear) oblivious routings. Rather than constructing the circulation projection matrix directly, we show how the efficient construction of an oblivious routing algorithm with a good competitive ratio immediately allows us to produce a circulation projection matrix.

In the remainder of this section, we formally define oblivious routings and prove the relationship between oblivious routing and circulation projection matrices (Section 4.1), provide a high level overview of our recursive approach and state the main theorems we will prove in later sections (Section 4.2). Finally, we prove the main theorem about our almost-linear-time construction of circulation projection with norm $2^{O(\sqrt{\log(n)\log\log(n)})}$ assuming the proofs in the later sections (Section 4.3).

Here we provide definitions and prove basic properties of oblivious routings, that is, fixed mappings from demands to flows that meet the input demands. While non-linear algorithms could be considered, we restrict our attention to linear oblivious routing strategies and use the term oblivious routing to refer to the linear subclass for the remainder of the paper.Note that the oblivous routing strategies considered in are all linear oblivious routing strategies.

Oblivious routings get their name due to the fact that, given an oblivious routing strategy $\mathbf{A}$ and a set of demands $D=\{\vec{\chi}_{1},\ldots,\vec{\chi}_{k}\},$ one can construct a multicommodity flow satisfying all the demands in $D$ by using $\mathbf{A}$ to route each demand individually, obliviously to the existence of the other demands. We measure the competitive ratioAgain note that here and in the rest of the paper we focus our analysis on competitive ratio with respect to norm $\|\cdot\|_{\infty}$. However, many of the results present are easily generalizable to other norms. These generalizations are outside the scope of this paper. of such an oblivious routing strategy to be the ratio of the worst relative congestion of such a routing to the minimal-congestion routing of the demands.

At times, it will be more convenient to analyze an oblivious routing as a linear algebraic object rather a combinatorial algorithm; towards this end, we note that the competitive ratio of a linear oblivious routing strategy can be gleaned from the operator norm of a related matrix (see also and ). Below, we state and prove a generalization of this result to weighted graphs that will be vital to relating $\mathbf{A}$ to $\widetilde{\mathbf{P}}$.

For any oblivious routing $\mathbf{A},$ we have $\rho(\mathbf{A})=\|\mathbf{U}^{-1}\mathbf{A}\mathbf{B}^{T}\mathbf{U}\|_{\infty}$

To make this lemma easily applicable in a variety of settings, we make use of the following easy to prove lemma.

The previous two lemmas make the connection between oblivious routings and circulation projection matrices clear. Below, we prove it formally.

Next, we check that $\widetilde{\mathbf{P}}$ is the identity on cycle space

2. A Recursive Approach by Embeddings

We construct an oblivious routing for a graph recursively. Given a generic, possibly complicated, graph, we show how to reduce computing an oblivious routing on this graph to computing an oblivious routing on a simpler graph on the same vertex set. A crucial concept in these constructions will be the notion of an embedding, which will allow us to relate the competitive ratios of an oblivious routing algorithms over graphs on the same vertex sets but different edge sets.

In other words, an embedding is a map from flows in one graph $G$ to flows in another graph $G^{\prime}$ that preserves the demands met by the flow. We can think of an embedding as a way of routing any flow in graph $G$ into graph $G^{\prime}$ that has the same vertex set, but different edges. We will be particularly interested in embeddings that increase the congestion of the flow by a small amount going from $G$ to $G^{\prime}$.

Embeddings potentially allow us to reduce computing an oblivious routing in a complicated graph to computing an oblivious routing in a simpler graph. Specifically, if we can embed a complicated graph in a simpler graph and we can efficiently embed the simple graph in the original graph, both with low congestion, then we can just focus on constructing oblivious routings in the simpler graph. We prove this formally as follows.

To bound $\rho(A),$ we let $\mathbf{U}$ denote the capacity matrix of $G$ and $\mathbf{U}^{\prime}$ denote the capacity matrix of $G^{\prime}$. Using Lemma 10, we get

Using that $\mathbf{M}$ is an embedding and therefore ${\mathbf{B}^{\prime}}^{T}\mathbf{M}=\mathbf{B}^{T}$, we get

By the definition of competitive ratio and congestion, we obtain the result. ∎

Note how in this lemma we only use the embedding from $G$ to $G^{\prime}$ to certify the quality of flows in $G^{\prime}$, we do not actually need to apply this embedding in the reduction.

Using this concept, we construct oblivious routings via recursive application of two techniques. First, in Section 5 we show how to take an arbitrary graph $G=(V,E)$ and approximate it by a sparse graph $G^{\prime}=(V,E^{\prime})$ (i.e. one in which $|E^{\prime}|=\widetilde{O}(|V|)$) such that flows in $G$ can be routed in $G^{\prime}$ with low congestion and that there is an $\widetilde{O}(1)$ embedding from $G^{\prime}$ to $G$ that can be applied in $\widetilde{O}(|E|)$ time. We call such a construction a flow sparsifiers and prove the following theorem.

Let $G=(V,E,\vec{\mu})$ be an undirected capacitated graph with capacity ratio $U\leq\poly(|V|)$. In $\widetilde{O}(|E|)$ time we can construct a graph $G^{\prime}$ on the same vertex set with at most $\widetilde{O}(|V|)$ edges and capacity ratio at most $U\cdot\poly(|V|).$ Moreover, given an oblivious routing $\mathbf{A}^{\prime}$ on $G^{\prime},$ in $\widetilde{O}(|E|)$ time we can construct an oblivious routing $\mathbf{A}$ on $G$ such that

Next, in Section 6 we show how to embed a graph into a collection of graphs consisting of trees plus extra edges. Then, we will show how to embed these graphs into better structured graphs consisting of trees plus edges so that by simply removing degree 1 and degree 2 vertices we are left with graphs with fewer vertices. Formally, we prove the following.

Let $G=(V,E,\vec{\mu})$ be an undirected capacitated graph with capacity ratio $U$. For all $t>0$ in $\widetilde{O}(t\cdot|E|)$ time we can compute graphs $G_{1},\ldots,G_{t}$ each with at most $\widetilde{O}(\frac{|E|\log(U)}{t})$ vertices, at most $|E|$ edges, and capacity ratio at most $|V|\cdot U.$ Moreover, given oblivious routings $\mathbf{A}_{i}$ for each $G_{i}$, in $\widetilde{O}(t\cdot|E|)$ time we can compute an oblivious routing $\mathbf{A}$ on $G$ such that

In the next section we show that the careful application of these two ideas along with a powerful primitive for routing on constant sized graphs suffices to produce an oblivious routing with the desired properties.

3. Efficient Oblivious Routing Construction Proof

First, we provide the lemma that will serve as the base case of our recursion. In particular, we show that electric routing can be used to obtain a routing algorithm with constant competitive ratio for constant-size graphs.

Assuming Theorem 16 and Theorem 17, which we prove in the next two sections, we prove that low-congestion oblivious routings can be constructed efficiently.

Given an undirected capacitated graph $G=(V,E,\vec{\mu})$ with capacity ratio $U$. Assume $U=\poly(|V|)$. We can construct an oblivious routing algorithm $\mathbf{A}$ on $G$ in time

Repeat this process on each $G_{i}^{(1)}$, it produces $t^{2}$ graphs $G_{1}^{(2)},\cdots,G_{t^{2}}^{(2)}$. Keep doing this until all graphs $G_{i}$ produced have $O(1)$ vertices. Let $k$ be the highest level we go through in this process. Since at the $k$-th level the number of vertices of each graph is at most $O\left(\frac{1}{t^{k}}|E|\log^{2kc}|V|\log^{2k}(U|V|^{2ck})\right)$ vertices, we have $k=O\left(\sqrt{\frac{\log|V|}{\log\log|V|}}\right)$.

On each graph $G_{i}$, we use Theorem 18 to get an oblivious routing algorithm $\mathbf{A}_{i}$ for each $G_{i}$ with

Then, the Theorem 17 and 16 shows that we have an oblivious routing algorithm $\mathbf{A}$ for $G$ with

The result follows from $k=O\left(\sqrt{\frac{\log|V|}{\log\log|V|}}\right)$ and $t=\left\lceil 2^{\sqrt{\log|V|\log\log|V|}}\right\rceil$. ∎

Using Theorem 19, Lemma 12 and Theorem 4, we have the following almost linear time max flow algorithm on undirected graph.

Given an undirected capacitated graph $G=(V,E,\vec{\mu})$ with capacity ratio $U$. Assume $U=\poly(|V|)$. There is an algorithm finds an $(1-\varepsilon)$ approximate maximum flow in time

Flow Sparsifiers

In order to prove Theorem 16, i.e. reduce the problem of efficiently computing a competitive oblivious routing on a dense graph to the same problem on a sparse graph, we introduce a new algorithmic tool called flow sparsifiers. Note that our flow sparsifiers aim to reduce the number of edges, and are different from the flow sparsifiers of Leighton and Moitra , which work in a different setting and reduce the number of vertices. A flow sparsifier is an efficient cut-sparsification algorithm that also produces an efficiently-computable low-congestion embedding mapping the sparsified graph back to the original graph.

Sparsity: $G^{\prime}$ is $h$-sparse, i.e.

Cut Approximation: $G^{\prime}$ is an $\varepsilon$-cut approximation of $G,$ i.e.

Flow Approximation: $\mathbf{M}$ has congestion at most $\alpha,$ i.e.

Flow sparsifiers allow us to solve a multi-commodity flow problem on a possibly dense graph $G$ by converting $G$ into a sparse graph $G^{\prime}$ and solving the flow problem on $G^{\prime}$, while suffering a loss of a factor of at most $\alpha$ in the congestion when mapping the solution back to $G$ using $\mathbf{M}.$

Consider a graph $G=(V,E,\mu)$ and let $G^{\prime}=(V,E^{\prime},\mu^{\prime})$ be given by an $(h,\varepsilon,\alpha)$-flow sparsifier of $G.$ Then, for any set of $k$ demands $D=\{\vec{\chi}_{1},\vec{\chi}_{2},\ldots,\vec{\chi}_{k}\}$ between vertex pairs of $V,$ we have:

Given the optimum flow $\{f^{\star}_{i}\}$ over $G^{\prime}$, we have

By the flow-cut gap theorem of Aumann and Rabani , we have that, for any set of $k$ demands $D$ on $V$ we have:

where $D(\partial(S))$ denotes the total amount of demand separated by the cut between $S$ and $\bar{S}.$ As any cut $S\subseteq V$ in $G^{\prime}$ has capacity $\mu^{\prime}(\partial_{G^{\prime}}(S))\geq(1-\varepsilon)\mu(\partial_{G}(S)),$ we have:

The second part of the theorem follows as a consequence of the definition of the congestion of the embedding $\mathbf{M}.$ ∎

Our flow sparsifiers should be compared with the cut-based decompositions of Räcke . Räcke constructs a probability distribution over trees and gives explicit embeddings from $G$ to this distribution and backwards, achieving a congestion of $O(\log n).$ However, this distribution over tree can include up to $O(m\log n)$ trees and it is not clear how to use it to obtain an almost linear time algorithm. Flow sparsifiers answer this problem by embedding $G$ into a single graph $G^{\prime}$, which is larger than a tree, but still sparse. Moreover, they provide an explicit efficient embedding of $G^{\prime}$ into $G.$ Interestingly, the embedding from $G$ to $G^{\prime}$ is not necessary for our notion of flow sparsifier, and is replaced by the cut-approximation guarantee. This requirement, together with the application of the flow-cut gap , lets us argue that the optimal congestion of a $k$-commodity flow problem can change at most by a factor of $O(\log k)$ between $G$ and $G^{\prime}.$

The main goal of this section will be to prove the following theorem:

Assuming Theorem 23, we can now prove Theorem 16, the main theorem necessary for edge reduction in our construction of low-congestion projections.

To complete the proof, we bound the competivite ratio $\rho(\mathbf{A}).$ Using the same argument as in Lemma 10, we can write $\rho(\mathbf{A})$ as

0.2. Techniques

In the next two subsections, we introduce the necessary concept about electrical-flow routing and prove that it achieves low competitive ratio over near-expanders (and subsets of near-expanders).

1. Subgraph Routing

Note that $\mathbf{A}$ may use all the edges in $G$ but $\rho^{F}(\mathbf{A})$ compares it only against routings that are restricted to use only edges in $F$. As before, we can upper bound the $F$-competitive ratio $\rho^{F}(\mathbf{A})$ by operator norms.

2. Electrical-Flow Routings

In this section, we define the notion of electrical-flow routing and prove the results necessary to construct flow sparsifiers. Recall that $\mathbf{R}$ is the diagonal matrix of resistances and the Laplacian $\mathbf{\mathcal{L}}$ is defined as $\mathbf{B}^{T}\mathbf{R}^{-1}\mathbf{B}.$ For the rest of this section, we assume that resistances are set as $\mathbf{R}=\mathbf{U}^{-1}.$

Consider a graph $G=(V,E,\mu)$ and set the edge resistances as $r_{e}=\frac{1}{\mu_{e}}$ for all $e\in E.$ The oblivious electrical-flow routing strategy is the linear operator $\mathbf{A}_{\mathcal{E}}$ defined as

In words, the electrical-flow routing strategy is the routing scheme that, for each demand $\vec{\chi}$ sends the electrical flow with boundary condition $\vec{\chi}$ on the graph $G$ with resistances $\mathbf{R}=\mathbf{U}^{-1}.$

For the electrical-flow routing strategy $\mathbf{A}_{\mathcal{E}}$, the upper bound on the competitive ratio $\rho(\mathbf{A}_{\mathcal{E}})$ in Lemma 10 can be rephrased in terms of the voltages induced on $G$ by electrically routing an edge $e\in E.$ This interpretation appears in .

The same reasoning can be extended to the subgraph-routing case to obtain the following lemma.

For $F\subseteq E$ and $\mathbf{R}=\mathbf{U}^{-1}$ we have

In this section, we prove that we can bound the $F$-competitive ratio of the oblivious electrical-routing strategy as long as the edges $F$ that the optimum flow is allowed to route over are contained within an induced expander $G(U)=(U,E(U))$ for some $U\subseteq V$ . Towards this we provide and prove the following lemma. This is a generalization of a similar lemma proved in .

For weighted graph $G=(V,E,w)$ with integer weights and vertex subset $U\subseteq V$ the following holds:

Since adding a multiple of the all-ones vector to $v$ does not change the quantity of interest in Equation 3, we can assume without loss of generality that

For any vertex subset $S\subseteq U,$ we denote the flow out of $S$ and the weight out of $S$ by

In words, the $c_{i+1}$ equals the sum of $c_{i}$ and an increase $\Delta_{i}$ which depends on how much the cut $\delta(C_{i})\cap E(U)$ was congested by the electrical flow.

By repeating the same argument on $S_{0}^{\leq},$ we get that $\sum_{a\in S_{0}^{\leq}}d(a)v(a)\leq\frac{2r}{\Phi(G(U))}$. Putting this all together yields

From this lemma and Lemma 27, the following is immediate:

Let $F\subseteq E$ be contained within some vertex induced subgraph $G(U),$ then for $\mathbf{R}=\mathbf{U}^{-1}$ we have

3. Construction and Analysis of Flow Sparsifiers

In the remainder of this section we show how to produce an efficient $O(\log^{c})$-flow sparsifier for some fixed constant $c,$ proving Theorem 23. In this version of the paper, we make no attempt to optimize the value of $c.$ For the rest of this section, we again assume that we choose the resistance of an edge to be the the inverse of its capacity, i.e. $\mathbf{U}=\mathbf{W}=\mathbf{R}^{-1}.$

As discussed before, our approach follows closely that of Spielman and Teng to the construction of spectral sparsifiers. The first step of this line of attack is to reduce the problem to the unweighted case.

Given an $(h,\varepsilon,\alpha)$-flow-sparsifier algorithm for unweighted graphs, it is possible to construct an $(h\cdot\log U,\varepsilon,\alpha)$-flow-sparsifier algorithm for weighted graphs $G=(V,E,\mu)$ with capacity ratio $U$ obeying

The next step is to construct a routine which flow-sparsifies a constant fraction of the edges of $E.$ This routine will then be applied iteratively to produce the final flow-sparsifier.

$F$ contains most of the volume of $G,$ i.e.

The graph $H^{\prime}=(V,F^{\prime},w_{F^{\prime}})$ is an $\varepsilon$-cut approximation to $H=(V,F),$ i.e. for all $S\subseteq V:$

The embedding $\mathbf{H}$ from $H=(V,F^{\prime},w_{F^{\prime}})$ to $G$ has bounded congestion

Given Lemma 30 and Lemma 31, it is straightforward to complete the proof of Theorem 23.

By Lemma 31, at every iteration $t,$ $|F_{t}|\geq\frac{1}{2}\cdot|E_{t}|,$ so that $|E_{t+1}|\leq\frac{1}{2}\cdot|E_{t}|.$ This shows that there can be at most $T\leq\log(|E_{1}|)=O(\log n)$ iterations.

In words, $\mathbf{M}$ maps an edge $e^{\prime}\in E^{\prime}$ by finding $t$ for which $e^{\prime}\in F^{\prime}_{t}$ and applying the corresponding $\mathbf{H_{t}}.$

We are now ready to prove that this algorithm with output $G^{\prime}$ and $\mathbf{M}$ is an efficient $(\widetilde{O}(n),\varepsilon,\widetilde{O}(n))$-flow sparsifier. To bound the capacity ratio $U^{\prime}$ of $G^{\prime}$, we notice that

where we used the fact that the sets $F^{\prime}_{t}$ are disjoint and the guarantee on the range of $w_{F^{\prime}_{t}}.$

Next, we bound the sparsity of $G^{\prime}.$ By Lemma 31, $F^{\prime}_{t}$ contains at most $\widetilde{O}(n)$ edges. As a result, we get the required bound

For the cut approximation, we consider any $S\subseteq V.$ By the cut guarantee of Lemma 31, we have that, for all $t\in[T],$

Summing over all $t,$ as $E^{\prime}=\mathop{\dot{\bigcup}}F^{\prime}_{t}$ and $E=\mathop{\dot{\bigcup}}F_{t},$ we obtain the required approximation

The congestion of $\mathbf{M}$ can be bounded as follows

To conclude the proof, we address the efficiency of the flow sparsifier. The algorithm applies the routine of Lemma 31 for $T=\widetilde{O}(1)$ times and hence runs in time $\widetilde{O}(m),$ as required. Invoking the embedding $\mathbf{M}$ requires invoking each of the $T$ embeddings ${\mathbf{H_{t}}}.$ This takes time $\widetilde{O}(Tm)=\widetilde{O}(m).$

In this subsection, we prove Lemma 31. Our starting point is the following decomposition statement, which shows that we can form a partition of an unweighted graph where most edges do not cross the boundaries and the subgraphs induced within each set of this partition are near-expanders. The following lemma is implicit in Spielman and Teng’s local clustering approach to spectral sparsification .

For all $i,$ $S_{i}$ is contained in $V_{i}.$

For all $i,$ there exists a set $T_{i}$ with $S_{i}\subseteq T_{i}\subseteq V_{i},$ such that

At least half of the edges are found within the sets $\{S_{i}\},$ i.e.

Moreover, the spectral sparsification of constructs the weights $\{w^{\prime}_{i}(e)\}_{e\in E^{\prime}_{i}}$ such that

To complete the description of the algorithm, we output the partition $(F,\bar{F})$ of $E,$ where

We also output the set of weighted sparsified edges $F^{\prime}.$

The weight $w_{F^{\prime}}(e)$ of edge $e\in F^{\prime}$ is given by finding $i$ such that $e\in E^{\prime}_{i}$ and setting $w_{F^{\prime}}(e)=w^{\prime}_{i}(e).$

where $\mathbf{I}_{(E(V_{i}),E^{\prime}_{i})}$ is the identity mapping of the edges $E^{\prime}_{i}\subseteq E(V_{i})$ of $F^{\prime}$ over $V_{i}$ to the edges $E(V_{i})$ of $V_{i}$ in $G.$ Notice that there is no dependence on the resistances over $G$ as $G$ is unweighted.

This complete the description of the algorithm. We are now ready to give the proof of Lemma 31.

The algorithm described above performs a decomposition of the input graph $G=(V,E)$ in time $\widetilde{O}(m)$ by the Decomposition Lemma. By the result of Spielman and Srivastava , each $G_{i}$ is sparsified in time $\widetilde{O}(|E(S_{i})|).$ Hence, the sparsification step requires time $\widetilde{O}(m)$ as well. This shows that the algorithm runs in $\widetilde{O}(m)$-time, as required.

By the Decomposition Lemma, we know that $|F|=\sum_{i=1}^{k}|E(S_{i})|\geq\frac{|E|}{2},$ which satisfies the requirement of the Lemma. Moreover, by the spectral sparsification result, we know that $|F^{\prime}|=\sum_{i=1}^{k}|E^{\prime}_{i}|\leq\sum_{i=1}^{k}\widetilde{O}(|S_{i}|)\leq\widetilde{O}(n),$ as required. We also saw that by construction the weights $w_{F^{\prime}}$ are bounded:

To obtain the cut-approximation guarantee, we use the fact that for every $i,$ by spectral sparsification,

We have $H^{\prime}=(V,F^{\prime},w_{F^{\prime}})$ and $H=(V,F).$ Consider now $T\subseteq V$ and apply the previous bound to $T\cap S_{i}$ for all $i.$ Because $F^{\prime}\subseteq F=\cup_{i=1}^{k}E(S_{i}),$ we have that summing over the $k$ bounds yields

which is the desired cut-approximaton guarantee.

Finally, we are left to prove that the embedding $\mathbf{H}$ from $H^{\prime}=(V,F^{\prime},w_{F^{\prime}})$ to $G=(V,E)$ has low congestion and can be applied efficiently. By definition of congestion,

When we route $D_{i}$ oblivious in $G(V_{i})$, we can consider the $E(S_{i})$-competitive ratio $\rho^{E(S_{i})}({\mathbf{A}_{\mathcal{E}}}_{,i})$ of the electrical routing ${\mathbf{A}_{\mathcal{E}}}_{,i}=\mathbf{B}_{E(V_{i})}{\mathbf{\mathcal{L}}}^{\dagger}_{G(V_{i})},$ as $D_{i}$ is routable in $E(S_{i}),$ because $E^{\prime}_{i}\subseteq E(S_{i}).$ We have

Finally, putting these bounds together, we have:

But, by the Decomposition Lemma, there exists $T_{i}$ with $S_{i}\subseteq T_{i}\subseteq V_{i}$ such that

Removing Vertices in Oblivious Routing Construction

In this section we show how to reduce computing an efficient oblivious routing on a graph $G=(V,E)$ to computing an oblivious routing for $t$ graphs with $\widetilde{O}(\frac{|V|}{t})$ vertices and at most $|E|$ edges. Formally we show

We break this proof into several parts. First we show how to embed $G$ into a collection of $t$ graphs consisting of trees minus some edges which we call patrial tree embeddings (Section 6.1). Then we show how to embed a partial tree embedding in an “almost $j$-tree” , that is a graph consisting of a tree and a subgraph on at most $j$ vertices, for $j=2t$ (Section 6.2). Finally, we show how to reduce oblivious routing on an almost $j$-tree to oblivious routing on a graph with at most $O(j)$ vertices by removing degree-1 and degree-2 vertices (Section 6.3). Finally, in Section 6.4 we put this all together to prove Theorem 17.

We remark that much of the ideas in the section were either highly influenced from or are direct restatements of theorems from adapted to our setting. We encourage the reader to look over that paper for further details regarding the techniques used in this section.

To prove Theorem 17, we make heavy use of spanning trees and various properties of them. In particular, we use the facts that for every pair of vertices there is a unique tree path connecting them, that every edge in the tree induces a cut in the graph, and that we can embed a graph in a tree by simply routing ever edge over its tree path and that the congestion of this embedding will be determined by the load the edges place on tree edges. We define these quantities formally below.

For undirected $G=(V,E)$ and spanning tree $T\subseteq E$ the edges cut by $e$, $\partial_{T}(F)$, and the edges cut by $F$, $\partial_{T}(e)$, are given by

While these properties do highlight the fact that we could just embed our graph into a collection of trees to simplify the structure of our graph, this approach suffers from a high computational cost . Instead we show that we can embed parts of the graph onto collections of trees at a lower computational cost but higher complexity. In particular we will consider what we call partial tree embeddings.

For undirected capacititated graph $G=(V,E,\vec{\mu})$, spanning tree $T$ and spanning tree subset $F\subseteq T$ we define the partial tree embedding graph $H=H(G,T,F)=(V,E^{\prime},\vec{\mu}^{\prime})$ to a be a graph on the same vertex set where $E^{\prime}=T\cup\partial_{T}(F)$ and

For any undirected capacitated graph $G=(V,E,\vec{\mu})$ and any $t>0$ in $\widetilde{O}(t\cdot m)$ time we can find a collection of partial tree embeddings $H_{1}=H(G,T_{1},F_{1}),\ldots,H_{t}=H(G,T_{t},F_{t})$ and coefficients $\lambda_{i}\geq 0$ with $\sum_{i}\lambda_{i}=1$ such that $\forall i\in[t]$ we have $|F_{i}|=\widetilde{O}(\frac{m\log U}{t})$ and such that $\sum_{i}\lambda_{i}\mathbf{M}^{\prime}_{H_{i}}$ embeds $G^{\prime}=\sum_{i}\lambda_{i}G_{i}$ into $G$ with congestion $\widetilde{O}(1)$.

Using this lemma, we can prove that we can reduce constructing an oblivious routing for a graph to constructing oblivious routings on several partial tree embeddings.

Let the $H_{i}$ be graphs produced by Lemma 38 and for all $i$ let $\mathbf{A}_{i}$ be an oblivious routing algorithm for $H_{i}$. It follows that $\mathbf{A}=\sum_{i}\lambda_{i}\mathbf{M}^{\prime}_{H_{i}}\mathbf{A}_{i}$ is an oblivious routing on $G$ with $\rho(\mathbf{A})\leq\widetilde{O}(\max_{i}\rho(\mathbf{A}_{i})\log n)$ and $\mathcal{T}\left(\mathbf{A}\right)=O(\sum_{i}\mathcal{T}\left(\mathbf{A}_{i}\right))$

The proof is similar to the proof of Lemma 15. For all $i$ let $\mathbf{U}_{i}$ denote the capacity matrix of graph $G_{i}$. Then using Lemma 10 we get

Using that $\mathbf{M}_{H_{i}}$ is an embedding and therefore $\mathbf{B}^{T}_{H_{i}}\mathbf{M}_{H_{i}}=\mathbf{B}^{T}$ we get

2. From Partial Tree Embeddings To Almost-j-trees

Here we show how to reduce constructing an oblivious routing for a partial tree embedding to constructing an oblivious routing for what Madry calls an “almost $j$-tree,” the union of a tree plus a subgraph on at most $j$ vertices. First we define such objects and then we prove the reduction.

We call a graph $G=(V,E)$ an almost $j$-tree if there is a spanning tree $T\subseteq E$ such that the endpoints of $E\setminus T$ include at most $j$ vertices.

For every $e=(a,b)\in E$, we let $v^{1}(e)\in V$ denote the first vertex on tree path $P_{(a,b)}$ incident to $F$ and we let $v^{2}(e)\in V$ denote the last vertex incident to $F$ on tree path $P_{(a,b)}$. Note that for every $e=(a,b)\in T$ we have that $(v^{1}(e),v^{2}(e))=e$.

We define $G^{\prime}=(V,E^{\prime},\vec{\mu}^{\prime})$ to simply be the graph that consists of all these $(v^{1}(e),v^{2}(e))$ pairs

and we define the weights to simply be the sums

Now to embed $H$ in $G^{\prime}$ we define $\mathbf{M}$ by

and to embed $G^{\prime}$ in $H$ we define $\mathbf{M}^{\prime}$ by

In other words we route edges in $H$ along the tree until we encounter nodes in $F$ and then we route them along added edges and we simply route the other way for the reverse embedding. By construction clearly the congestion of the embedding in either direction is 2.

To bound the running time, we note that by having every edge $e$ in $H$ maintain its $v^{1}(e)$ and $v^{2}(e)$ information, having every edge $e^{\prime}$ in $E^{\prime}$ maintain the set $\{e\in E|e^{\prime}=(v^{1}(e),v^{2}(e))\}$ in a list, and using link cut trees or the static tree structure in to update information along tree paths we can obtain the desired value of $\mathcal{T}\left(\mathbf{M}^{\prime}\right)$. ∎

3. From Almost-J Trees to Less Vertices

Here we show that by “greedy elimination” , i.e. removing all degree 1 and degree 2 vertices in $O(m)$ time we can reduce oblivious routing in almost-$j$-trees to oblivious routing in graphs with $O(j)$ vertices while only losing $O(1)$ in the competitive ratio. Again, we remark that the lemmas in this section are derived heavily from but repeated for completeness and to prove additional properties that we will need for our purposes.

We start by showing that an almost-$j$-tree with no degree 1 or degree 2 vertices has at most $O(j)$ vertices.

For any almost $j$-tree $G=(V,E)$ with no degree 1 or degree 2 vertices, we have $|V|\leq 3j-2$.

Since $G$ is an almost $j$-tree, there is some $J\subseteq V$ with $|J|\leq j$ such that the removal of all edges with both endpoints in $J$ creates a forest. Now, since $K=V-J$ is incident only to forest edges clearly the sum of the degrees of the vertices in $K$ is at most $2(|V|-1)$ (otherwise there would be a cycle). However, since the minimum degree in $G$ is 3, clearly this sum is at least $3(|V|-j)$. Combining yields that $3|V|-3j\leq 2|V|-2$. ∎

Next, we show how to remove degree one vertices efficiently.

Let $G=(V,E,\vec{\mu})$ be an unweighted capacitated graph, let $a\in V$ be a degree 1 vertex, let $e=(a,b)\in E$ be the single edge incident to $a$, and let $G^{\prime}=(V^{\prime},E^{\prime},\vec{\mu}^{\prime})$ be the graph that results from simply removing $e$ and $a$, i.e. $V^{\prime}=V\setminus\{a\}$ and $E^{\prime}=E\setminus\{e\}$. Given $a\in V$ and an oblivious routing algorithm $\mathbf{A}^{\prime}$ in $G^{\prime}$ in $O(1)$ time we can construct an oblivious routing algorithm $\mathbf{A}$ in $G$ such that

For any demand vector $\vec{\chi}$, the only way to route demand at $a$ in $G$ is over $e$. Therefore, if $\mathbf{B}\vec{f}=\vec{\chi}$ then $\vec{f}(e)=\vec{\chi}$. Therefore, to get an oblivious routing algorithm on $G$, we can simply send demand at $a$ over edge $e$, modify the demand at $b$ accordingly, and then run the oblivious routing algorithm on $G^{\prime}$ on the remaining vertices. The routing algorithm we get is the following

Since all routing algorithms send this flow on $e$ we get that $\rho(\mathbf{A})=\rho(\mathbf{A}^{\prime})$ and since the above operators not counting $\mathbf{A}$ have only $O(1)$ entries that are not the identity we can clearly implement the operations in the desired running time. ∎

Using the above lemma we show how to remove all degree $1$ and $2$ vertices in $O(m)$ time while only increasing the congestion by $O(1)$.

Let $G=(V,E,\vec{\mu})$ be an unweighted capacitated graph and let $G^{\prime}=(V^{\prime},E^{\prime},\vec{\mu}^{\prime})$ be the graph the results from iteratively removing vertices of degree $1$ and replacing degree $2$ vertices with an edge connecting its neighbors of the minimum capacity of its adjacent edges. We can construct $G^{\prime}$ in $O(m)$ time and given an oblivious routing algorithm $\mathbf{A}^{\prime}$ in $G^{\prime}$ in $O(1)$ time we can construct an oblivious routing algorithm $\mathbf{A}$ in $G$ such that Note that the constant of 4 below is improved to 3 in .

First we repeatedly apply Lemma 43 repeatedly to in reduce to the case that there are no degree 1 vertices. By simply array of the degrees of every vertex and a list of degree 1 vertices this can be done in $O(m)$ time. We denote the result of these operations by graph $K$.

Next, we repeatedly find degree two vertices that have not been explored and explore this vertices neighbors to get a path of vertices, $a_{1},a_{2},\ldots,a_{k}\in V$ for $k>3$ such that each vertex $a_{2},\ldots,a_{k-1}$ is of degree two. We then compute $j=\operatorname*{arg\,min}_{i\in[k-1]}\vec{\mu}(a_{i},a_{i+1})$, remove edge $(a_{j},a_{j+1})$ and add an edge $(a_{1},a_{k})$ of capacity $\vec{\mu}(a_{j},a_{j+1})$. We denote the result of doing this for all degree two vertices by $K^{\prime}$ and note that again by careful implementation this can be performed in $O(m)$ time.

Note that clearly $K$ is embeddable in $K^{\prime}$ with congestion 2 just by routing every edge over itself except the removed edges which we route by the path plus the added edges. Furthermore, $K^{\prime}$ is embeddable in $K$ with congestion 2 again by routing every edge on itself except for the edges which we added which we route back over the paths they came from. Furthermore, we note that clearly this embedding and the transpose of this operator is computable in $O(m)$ time.

Finally, by again repeatedly applying Lemma 43 to $K^{\prime}$ until there are no degree 1 vertices we get a graph $G^{\prime}$ that has no degree one or degree two vertices (since nothing decreased the degree of vertices with degree more than two). Furthermore, by Lemma 43 and by Lemma 15 we see that we can compose these operators to compute $\mathbf{A}$ with the desired properties. ∎

4. Putting It All Together

Here we put together the previous components to prove the main theorem of this section.

Using Lemma 38 we can construct $G^{\prime}=\sum_{i=1}^{t}\lambda_{i}G_{i}$ and embeddings $\mathbf{M}_{1},\ldots,\mathbf{M}_{t}$ from $G_{i}$ to $G$. Next we can apply Lemma 41 to each $G_{i}$ to get almost-$j$-trees $G^{\prime}_{1},\ldots,G^{\prime}_{t}$ and embeddings $\mathbf{M}^{\prime}_{1},\ldots,\mathbf{M}^{\prime}_{t}$ from $G^{\prime}_{i}$ to $G_{i}$. Furthermore, using Lemma 44 we can construction graphs $G^{\prime\prime}_{1},\ldots,G^{\prime\prime}_{t}$ with the desired properties (the congestion ratio property follows from the fact that we only add capacities during these reductions)

Nonlinear Projection and Maximum Concurrent Flow

In this section, we strengthen and generalize the MaxFlow algorithm to a more general setting. We believe this algorithm may be of independent interest as it includes maximum concurrent flow problem, the compressive sensing problem, etc. For some norms, e.g. $\|\cdot\|_{1}$ as typically of interest compressive sensing, the Nesterov algorithm can be used to replace gradient descent. However, this kind of accelerated method is not known in the general norm settings as good proxy function may not exist at all. Even worse, in the non-smooth regime, the minimization problem on the $\|\cdot\|_{p}$ space with $p>2$ is difficult under some oracle assumption . For these reasons we focus here on the gradient descent method which is always applicable.

Given a norm $\|\cdot\|$, we wish to solve the what we call the non-linear projection problem

where $\vec{y}$ is an given point and $L$ is a linear subspace. We assume the following:

There are a family of convex differentiable functions $f_{t}$ such that for all $\vec{x}\in L$, we have

and the Lipschitz constant of $\nabla f_{t}$ is $\frac{1}{t}$.

There is a projection matrix $\mathbf{P}$ onto the subspace $L$.

In other words we assume that there is a family of regularized objective functions $f_{t}$ and a projection matrix $\mathbf{P}$, which we can think of as an approximation algorithm of this projection problem.

Now, let $\vec{x}^{*}$ be a minimizer of $\min_{\vec{x}\in L}\|\vec{x}-\vec{y}\|$. Since $\vec{x}^{*}\in L$, we have $\mathbf{P}\vec{x}^{*}=\vec{x}^{*}$ and hence

Therefore, the approximation ratio of $\mathbf{P}$ is $1+\|\mathbf{P}\|$ and we see that our problem is to show that we can solve nonlinear projection using a decent linear projection matrix. Our algorithm for solving this problem is below.

Note that this algorithm and its proof are quite similar to Theorem 4 but modified to scale parameters over an outer loop. By changing the parameter $t$ we can decrease the dependence of the initial error.This is an idea that has been applied previously to solve linear programming problems .

Assume the conditions in Assumption 45 are satisfied. Let $\mathcal{T}$ be the time needed to compute $\mathbf{P}x$ and $\mathbf{P}^{T}x$ and ${x}^{\#}$. Then, NonlinearProjection outputs a vector $\vec{x}$ with $\|\vec{x}\|\leq(1+\varepsilon)\min_{\vec{x}\in L}\|\vec{x}-\vec{y}\|$ and the algorithm takes time

We prove by induction on $j$ that when $2^{-(j-1)}\|\mathbf{P}\|\geq 1$ we have $\|\vec{y_{j}}\|\leq\left(1+2^{-j}\|\mathbf{P}\|\right)\text{OPT}$.

For the base case ($j=0$), (46) shows that $\|\vec{y_{0}}\|\leq\left(1+\|\mathbf{P}\|\right)\text{OPT}.$

For the inductive case we assume that the assertion holds for some $j$. We start by bounding the corresponding $R$ in Theorem 1 for $g_{j}$, which we denote $R_{j}$. Note that