Simpler and Faster Directed Low-Diameter Decompositions

Jason Li · 2025

Read Simpler and Faster Directed Low-Diameter Decompositions by Jason Li (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-2505-10244.txt.

Introduction

Jason Li presents a simpler and faster algorithm for splitting directed graphs in this 2025 paper. A low diameter decomposition breaks a directed graph into clusters of small diameter. Such splits are a basic tool in graph algorithms. A 2025 result set the best known loss factor for the task, but with a slower method.

Catalog record

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

Source: https://arxiv.org/abs/2505-10244

Browse the full library · About the Tower of Babel

Full text

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

Simpler and Faster Directed Low-Diameter Decompositions Jason Li Abstract We present a simpler and faster algorithm for low-diameter decompositions on directed graphs, matching the O ⁡ ( log ⁡ n ​ log ⁡ log ​ n ) O(\log n\log\log n) loss factor from Bringmann, Fischer, Haeupler, and Latypov (ICALP 2025) and improving the running time to O ⁡ ( ( m + n ​ log ⁡ log ⁡ n ) ​ log 2 ​ n ) O((m+n\log\log n)\log^{2}n) . 1 Introduction We study the problem of computing a (probabilistic) low-diameter decomposition (LDD) on a directed graph: given a diameter parameter \Delta , delete a random subset of edges such that (1) each strongly connected component in the remaining graph has weak diameter at most \Delta , and (2) each edge is deleted with probability at most \ell(n)/\Delta times the weight of the edge, where \ell(n) is a loss factor that should be minimized. Historically, LDDs were first studied on undirected graphs, where it has become a central tool in the design of graph algorithms [ LS93 , Bar96 ] , especially in constrained computational models such as parallel [ BGK+11 , MPX13 ] , distributed [ AGLP89 , ABCP92 ] , and dynamic [ FG19 , CZ20 ] . For directed graphs, a non-probabilistic version of LDDs was studied in the context of directed feedback vertex set [ Sey95 ] , minimum multi-cut [ KPRT97 ] , and multi-commodity flow [ LR99 ] , though its presence was limited in the following two decades until the seminal result of Bernstein, Nanongkai, and Wulff-Nilsen [ BNWN25 ] , who used (probabilistic) directed LDDs to obtain the first near-linear time algorithm for negative-weight single-source shortest paths. They devised a simple directed LDD algorithm that achieved a loss factor of \ell(n)=O(\log^{2}n) , though optimizing this bound was not their main focus. Directed LDDs were then systematically studied by Bringmann, Fischer, Haeupler, and Latypov [ BFHL25 ] , who improved the bound to \ell(n)=O(\log n\log\log n) , coming close to the \Omega(\log n) lower bound which also holds for undirected graphs. They also designed a randomized algorithm achieving this bound that runs in O(m\log^{5}n\log\log n) time with high probability, 1 1 1 With high probability means with probability 1-1/n^{C} for arbitrarily large constant C>0 . and they remark that one logarithmic factor can be shaved by using a faster single-source shortest paths subroutine. In this work, we present a simpler and faster algorithm for directed LDDs, achieving the same bound \ell(n)=O(\log n\log\log n) and running in O((m+n\log\log n)\log^{2}n) time, an improvement of two logarithmic factors over the optimized version of [ BFHL25 ] . Theorem 1 . Given a graph with integral and polynomially-bounded edge weights, there is a directed LDD algorithm that achieves loss factor \ell(n)=O(\log n\log\log n) , runs in O((m+n\log\log n)\log^{2}n) time, and succeeds with high probability. 1.1 Preliminaries Let G=(V,E,w) be a directed graph with non-negative and integral edge weights. For a vertex subset U\subseteq V , define G[U] as the induced graph on U , and define E[U] as the edges of this induced graph. The degree of a vertex v\in V is the number of edges incident to v (which does not depend on the edge weights), and the volume \textup{vol}(U) of a vertex subset U\subseteq V equals \sum_{v\in U}\deg(v) . For vertices u,v\in V , define d(u,v) to be the distance from u to v according to the edge weights. For a vertex subset U\subseteq V , define the weak diameter of U as \max\{d(u,v):u,v\in U\} . For vertex t\in V and non-negative number r , define the out-ball B^{+}_{G}(t,r)=\{v\in V:d(t,v)\leq r\} and in-ball B^{-}_{G}(t,r)=\{v\in V:d(v,t)\leq r\} . We say that an edge (u,v) is cut by out-ball B^{+}_{G}(t,r) if u\in B^{+}_{G}(t,r) and v\notin B^{+}_{G}(t,r) , and it is cut by in-ball B^{-}_{G}(t,r) if v\in B^{-}_{G}(t,r) and u\notin B^{-}_{G}(t,r) . 1.2 Our Techniques Our algorithm follows the same template as [ BNWN25 , BFHL25 ] : compute an out-ball or in-ball B , remove the edges cut by the ball, and recursively solve the induced graphs G[B] and G[V\setminus B] . Observe that by removing all edges cut by B , the vertices in B can no longer share strongly connected components with the vertices in V\setminus B . Therefore, if the algorithm recursively computes directed LDDs in G[B] and G[V\setminus B] , which means deleting edges such that each strongly connected component has weak diameter at most \Delta , then deleting these same edges, along with the edges cut by the ball B , also produces strongly connected components with weak diameter at most \Delta in the original graph G . To bound the recursion depth and speed up the running time, the algorithms actually compute multiple balls in each recursive instance so that each recursive component has sufficiently fewer edges. The algorithm of [ BFHL25 ] adopts a specialized recursive structure colloquially known as Seymour’s trick [ Sey95 ] , and we use the same general approach. At a high level, our algorithm has two main differences which constitute the conceptual contributions of this paper. CKR instead of geometric ball-growing. The algorithm of [ BFHL25 ] uses the geometric ball-growing technique: sample a random radius from a geometric distribution, and cut the appropriate out-ball or in-ball. The main benefit of the geometric distribution is its memoryless property, which is crucial in bounding edge cut probabilities. On the other hand, to avoid losing another factor of O(\log n) in the bound of \ell(n) , the parameters are set in a way that the probability that the radius grows too large is larger than 1/\textup{poly}(n) , so it cannot be ignored with high probability and forces a delicate probability analysis. Instead, we adopt an approach first used by Calinescu, Karloff, and Rabani [ CKR00 ] in the context of LP rounding for multi-way cut. Here, the radius is no longer geometric, but uniformly random in a given range, and each ball uses the same sampled radius. The twist is that CKR computes the balls in a random order, which is key to their analysis. Similar to [ BFHL25 ] , we cannot afford to grow balls from all (remaining) vertices, which would incur a factor of O(\log n) in the bound of \ell(n) , so we also sample a subset of vertices from which to grow balls. On each application of CKR, for a given edge (u,v) , the cut probability has a factor that is logarithmic in the number of sampled vertices whose balls can possibly cut (u,v) . This factor is carefully balanced with the sizes of the recursive instances by an application of Seymour’s trick [ Sey95 ] . Elimination of heavy vertices. In the procedure of cutting balls, it is possible that the ball itself contains nearly all the vertices. In this case, the recursion depth can be large, affecting both the cut probability and running time. Our second contribution is a modular reduction to the special case where all out-balls and in-balls contain at most 75% of the edges. We remark that the threshold of 75% is arbitrary and can be replaced by any constant, even less than 50%. We expect this

Read the complete text