Local Sherman’s Algorithm for Multi-commodity Flow

Jason Li, Thatchaphol Saranurak · 2025

Read Local Sherman’s Algorithm for Multi-commodity Flow by Jason Li, Thatchaphol Saranurak (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-10632.txt.

Introduction

Jason Li and Thatchaphol Saranurak give a new flow algorithm in twenty twenty-five. Multi-commodity flow sends many goods through one network at once. Their algorithm is local, meaning it works from limited views rather than the whole graph. They apply it to expander graphs, networks that are very well connected.

On expanders, their method gives a near-exact approximation in time that breaks a long-standing barrier. All prior methods needed time tied to the product of commodities and edges, or settled for rough answers. Their trick localizes Sherman's algorithm inside a multiplicative weights frame. In each round, tiny weights are rounded to zero, so few large weights remain. The oracle call then runs in sublinear time. The insight may serve other problems too.

Catalog record

CREATORJason Li, Thatchaphol Saranurak
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE50 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-10632

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Local Sherman’s Algorithm for Multi-commodity Flow Jason Li, Thatchaphol Saranurak Abstract We give the first local algorithm for computing multi-commodity flow and apply it to obtain a ( 1 + ϵ ) (1+\epsilon) -approximate algorithm for computing a k k -commodity flow on an expander with m m edges in ( m + ϵ − 3 ​ k 3 ​ D ) ​ n o ⁡ ( 1 ) (m+\epsilon^{-3}k^{3}D)n^{o(1)} time, where D D is the total demand. This is the first ( 1 + ϵ ) (1+\epsilon) -approximate algorithm that breaks the k ​ m km multi-commodity flow barrier, albeit only on expanders. All previous algorithms either require Ω ⁡ ( k ​ m ) \Omega(km) time [ She17 ] or a big constant approximation [ HHL+24 ] . Our approach is by localizing Sherman’s flow algorithm [ She13 ] when put into the Multiplicative Weight Update (MWU) framework. We show that, on each round of MWU, the oracle could instead work with the rounded weights where all polynomially small weights are rounded to zero. Since there are only few large weights, one can implement the oracle call with respect to the rounded weights in sublinear time. This insight is generic and may be of independent interest. 1 Introduction The maximum flow problem is among the most central problems in combinatorial optimization. A long line of work [ FF56 , Din70 , GR98 , LS20 ] recently culminated in almost-linear time algorithms to solve maximum flow to high accuracy [ CKL+22 , VDBCP+23 ] , i.e., an (1+\epsilon) -approximation in time proportional to \textup{polylog}(1/\epsilon) . For low-accuracy solvers, i.e., time proportional to \textup{poly}(1/\epsilon) , a more recent series of developments [ CKM+11 , She13 ] culminated in the \tilde{O}(m/\epsilon) time algorithm of Sherman [ She17 ] for undirected graphs. Overall, the progress in the last decade has been astronomical in both accuracy regimes, and has greatly advanced the community’s understanding of this fundamental problem. The (concurrent) multi-commodity flow problem, on the other hand, is much less understood. Solving even 2 -commodity flow on directed graphs to high accuracy is as hard as solving general LPs [ DKZ22 ] , another major open problem in algorithm design. For dense graphs, algorithms faster than solving LPs are known [ vDBZ23 ] . In the low-accuracy regime, Sherman’s algorithm for undirected graphs directly translates to \tilde{O}(km/\epsilon) -time for k -commodity flow, which is already super-linear for moderate values of k . However, a dependency of km is difficult to avoid, as each of the k flows may use a linear number of edges, leading to a representation size of \Omega(km) for even outputting the flow. In the constant-approximation setting, a sparse implicit representation of multi-commodity flow was recently developed [ HHL+24 ] , leading to \tilde{O}((k+m)n^{\delta}) time algorithms with approximation factor \exp(\textup{poly}(1/\delta)) for any constant \delta>0 . It is unclear if we can hope to improve the approximation factor to (1+\epsilon) . Another orthogonal line of work focuses on local flow algorithms on unit-capacity graphs. A local algorithm runs in time sublinear in the input size, i.e., without reading the entire graph, and the unit-capacity setting makes local algorithms possible. During the last decade, researchers have localized many single-commodity flow algorithms including (binary) blocking flow algorithms [ OZ14 , NSY19 ] , augmenting path algorithms [ CHI+17 , FNS+20 ] , push-relabel algorithms [ HRW17 , SW19 , CMGS24 ] , and length-constrained flow algorithms [ HLS24 ] . These local algorithms found impressive applications in dynamic graph data structures and fast algorithms for expander decomposition and graph connectivity. All previous local algorithms except [ HLS24 ] , however, iteratively update the flow using the current residual graph. Thus, it is difficult to generalize to the multi-commodity setting where the different commodities may interact with each other. (While it is conceivable that the algorithm of [ HLS24 ] could be adapted to the multi-commodity setting, this algorithm is very involved.) Ultimately, there was no local algorithm for multi-commodity flow prior to our work. In this work, we give the first local algorithm for multi-commodity flow that either reports that the given demand is infeasible or feasibly routes this demand “almost completely” on each vertex. Theorem 1.1 (Informal version of Theorem 2.9 )) . There is an algorithm that, given a unit-capacity undirected graph G , a k -commodity demand b , and error parameter \epsilon , in O(\epsilon^{-2}\log n(\|b\|_{0}+\epsilon^{-1}\|b\|_{1})) time outputs either a certificate that the demand is infeasible or a feasible k -commodity flow whose residual demand on each vertex v for each commodity is at most \epsilon\deg(v) . Then, we apply our local algorithm to solve (1+\epsilon) -approximate k -commodity flow on a unit-capacity expander in time \approx m+\epsilon^{-3}k^{3}D , where D is the total demand. This is the first (1+\epsilon) -approximate k -commodity flow algorithm on expanders that breaks the km multi-commodity flow barrier (for moderate values of k and D ). Theorem 1.2 . Consider k pairs of tuples (s_{1},t_{1},d_{1}),\ldots,(s_{k},t_{k},d_{k})\in V\times V\times\mathbb{R}_{\geq 0} indicating that we want to send d_{j} units of commodity j\in[k] from s_{j} to t_{j} , and let \epsilon\in(0,1) be an error parameter. If G is a \phi -expander, then there is a deterministic algorithm that either certifies that there is no feasible k -commodity flow routing the demand, or computes a k -commodity flow with congestion 1+\epsilon . The algorithm runs in time (m+\epsilon^{-3}k^{3}D)\cdot\textup{poly}(1/\phi)\cdot 2^{O(\sqrt{\log n\log\log n})} where D=\sum_{j}d_{j} . Our results are obtained by localizing Sherman’s approximate maximum flow algorithm [ She13 ] . We remark that Sherman’s algorithm and our adaptation are also immediately parallelizable, though a recent parallel local algorithm based on push-relabel has also been discovered [ CMGS24 ] . 1.1 Our Techniques Our starting point is Sherman’s initial (or “unaccelerated”) \tilde{O}(m/\epsilon^{2}) time algorithm [ She13 ] with a trivial “preconditioner”, which we interpret in the Multiplicative Weights Update framework. (We assume no prior background of Sherman’s algorithm, and therefore do not discuss the role of preconditioning in Sherman’s algorithm.) At a high level, Sherman’s algorithm (with a trivial preconditioner) has a natural interpretation as follows. Each vertex has a potential that is initially 0 . On each of O(\epsilon^{-2}\log n) iterations, each edge independently sends full flow from the higher-potential endpoint to the lower-potential endpoint (with ties broken arbitrarily). Then, each vertex independently updates its potential based on how much flow it receives; note that potentials can be positive or negative. Intuitively, the more flow a vertex receives, the larger its new potential should be, since it should be more eager to push its flow outward on the next iteration. The actual update to potentials can be viewed as a step in Multiplicative Weights Update (MWU). Finally, at the end of the O(\epsilon^{-2}\log n) iterations, Sherman’s algorithm outputs the average of the flows computed on each iteration. Unfortunately, Sherman’s algorithm is not local because on each iteration, every edge sends full flow in some direction. One possible modification is to send no flow along an edge whose endpoints have equal potential, so in particular, the first flow is the empty flow. This change still guarantees correctness, but vertices can have different potentials very quickly into the algorithm, so the

Read the complete text