Abstract
Low diameter decompositions (LDDs) are a fundamental primitive in the design of efficient graph algorithms. Roughly speaking, an LDD is a distribution over partitions of the vertices into bounded-diameter clusters such that nearby vertices are likely to be clustered together. Recently, there has been growing interest in extending the notion of LDDs to directed graphs.
There are two natural directed analogues. The first is a directed LDD, where after removing a random subset of edges, every strongly connected component has a small diameter. The second is a quasipartition, which imposes a stronger requirement: whenever one vertex can still reach another after the edge removal, the two vertices must be close in the original directed metric. Every quasipartition yields an LDD, but the converse does not necessarily hold.
In this work, we initiate the systematic study of LDDs in structured directed graphs. Our first main result shows that any directed graph with pathwidth $\text{pw}$ admits an $(O(\text{pw}), \text{Δ})$-LDD. This improves upon the previous best-known $(2^{O(\text{pw}^2)}, \text{Δ})$-LDD construction, which was implicitly derived from the quasipartition result of Salmasi et al. [SODA'19].
Our second result shows that the integrality gap of the Directed Non-Bipartite Sparsest-Cut LP relaxation on an $n$-vertex graph with treewidth $\text{tw}$ is $O(\text{tw} \log n)$. This improves upon the $O(\text{tw} \log^2 n)$ bound of Mémoli et al. [ICALP'16, Algorithmica'18]. We obtain this result through the refined analysis of the quasipartition construction of Mémoli et al. for bounded treewidth graphs.
Blogger's Review: This paper makes significant contributions to low diameter decomposition in directed graphs, particularly by proposing new construction methods and improving existing bounds. This will have a profound impact on the design and analysis of future directed graph algorithms.