Near-Optimal Directed Low-Diameter Decompositions

It is easy to see that a loss factor of $L\ge 1$ is necessary: Consider a graph consisting of disjoint copies of $D+1$-cycles (of unit length, say). Any LDD is forced to cut at least one edge from every cycle, and thus some edges are deleted with probability $\frac{1}{D+1}$. In fact, from the same lower bound as for undirected graphs one can show that $L\ge \mathrm{\Omega }(\log n)$ is necessary¹¹1Specifically, using e.g., the probabilistic method, one can construct an undirected $n$-node graph $G$ with the following two properties: (i) the graph contains $cn$ edges (for some constant $c>1$), and (ii) the girth of $G$ (i.e., the length of the shortest cycle) is at least $g=\mathrm{\Omega }(\log n)$. Such a graph constitutes an obstruction against undirected LDDs with parameter $D=\frac{g}{2}-1$, say. Indeed, all connected components that remain after the LDD cuts edges cannot contain cycles (as any cycle contains two nodes at distance at least $\frac{g}{2}>D$). This means that all connected components are trees, and thus the remaining graph is a forest containing at most $n-1$ edges. Therefore, the LDD has cut at least $cn-n=\mathrm{\Omega }(n)$ edges. In particular, the per-edge cutting probability of some edges must be $\mathrm{\Omega }(1)=\mathrm{\Omega }(\log n/D)$. The same argument applies for directed LDDs by taking the same undirected graph and making all edges bidirected. for some directed graphs.

Conversely, Bernstein, Nanongkai and Wulff-Nilsen [16] showed that a loss of $O({\log }^{2}n)$ can be achieved. Their work leaves open whether this factor can be improved, possibly to $O(\log n)$ which would match the existing unconditional lower bound, or whether $\mathrm{\Omega }({\log }^{2}n)$ is necessary.

To be useful in algorithmic applications, it is necessary to be able to compute the LDD (or, formally speaking, to be able to sample from the LDD efficiently). This is a non-negligible problem as many graph decompositions are much simpler to prove existentially than constructively and efficiently – for instance, for Expander Decompositions there is a stark contrast between the extremely simple existential proof and the involved efficient algorithms based on cut-matching games [35, 30]. The $O({\log }^{2}n)$-loss LDD due to [16] is of course implementable by an efficient algorithm.

Another dimension is the distinction between “weak” and “strong” diameter guarantees. Specifically, Definition 1 requires the weak guarantee by requiring that any two nodes in the same strongly connected component are at distance at most $D$ in the original graph $G$. The strong version instead requires that each strongly connected component in $G\setminus S$ has diameter at most $D$ in the graph $G\setminus S$. While strong LDDs give a theoretically more appealing guarantee, for most algorithmic applications it turns out that weak LDDs suffice. The LDD developed by Bernstein, Nanongkai and Wulff-Nilsen [16] has a weak guarantee, but follow-up work [19] later extended their results to a strong LDD with cubic loss $O({\log }^{3}n)$.

In this paper, we will mostly ignore the distinction between weak and strong and follow Definition 1 as it is. We remark however that all of our existential results do in fact have the strong diameter guarantee.

Let us assume throughout that we only deal with unit-length graphs (i.e., where $\mathrm{\ell }(e)=1$ for all edges). This assumption is in fact without loss of generality, as we can simply replace each edge $e$ of length $\mathrm{\ell }(e)$ by a path of $\mathrm{\ell }(e)$ unit-length edges. This transformation may blow up the graph, but as we focus on the existential result first this shall not concern us.²²2We are assuming throughout that all edge weights are bounded by $\text{poly}(n)$, therefore this transformation leads to a graph on at most $n_0\le \text{poly}(n)$ nodes. In particular, to achieve a loss of $L=O(\log n\log \log n)$ on the original graph it suffices to achieve a loss of $O(\log n_0\log \log n_0)$ on the transformed graph. Whenever the LDD cuts at least one of the path edges in the transformed graph, we imagine that the entire edge in the original graph is cut. This way, when we cut each edge with probability at most $\frac{L}{D}$, in the original graph we cut each edge with probability at most $\frac{\mathrm{\ell }(e)\cdot L}{D}$ (by a union bound) as required.

Perhaps it appears surprising that we claim a connection between LDDs – which are inherently probabilistic objects – and EDs – which rather have a deterministic flavor. As a first step of bringing these notions together consider the following lemma based on the well-studied Multiplicative Weight Update [5] method.

Intuitively, the lemma states that in order to construct an LDD that cuts each edge with small probability $L/D$, it suffices to instead find a cut which globally minimizes the total cost of the cut edges while ensuring that every remaining strongly connected component has diameter at most $D$. This however comes with the price of introducing a cost function $c$ to the graph, and the goal becomes to cut edges which collectively have at most an $L/D$ fraction of the total cost. For the reader’s convenience, we include a quick proof sketch of Lemma 3.

In a leap forward, let us rename the costs $c$ to capacities $c$. Our idea is simple: We want to use an Expander Decomposition to remove edges of small total capacity so that all strongly connected components in the graph become expanders and thus, in particular, have small diameter.

To make this more precise, we first introduce some (standard) notation. A node set $U\subseteq V$ naturally induces a cut (between $U$ and $\overline{U}=V\setminus U$). We write $c(U,\overline{U})$ for the total capacity of edges crossing the cut from $U$ to $\overline{U}$, and define the volume of $U$ as

and also write $\mathrm{minvol}(U)=\min \{\mathrm{vol}(U),\mathrm{vol}(\overline{U})\}$. The sparsity of the cut $U$ is defined by

We say that $U$ is $\varphi$-sparse if $\varphi (U)\le \varphi$, and we call a graph without $\varphi$-sparse cuts a $\varphi$-expander. The standard Expander Decomposition can be stated as follows.

Moreover, an important property of a $\varphi$-expander decomposition is that the diameter of its strongly connected components depends on $\varphi$ in the following manner.

To understand the intuition behind Lemma 5, imagine that we grow a ball (i.e., a breadth-first search tree) around some node. With each step, the expansion property (related to the absence of $\varphi$-sparse cuts) guarantees that we increase the explored capacity by a factor of $(1+\varphi )$; thus after $O(\varphi \log \mathrm{vol}(V))$ steps we have explored essentially the entire graph.

Already at this point we have made significant progress and can recover the $O({\log }^{2}n)$-loss LDD: Apply the Expander Decomposition in Lemma 4 with parameter $\varphi =\log \mathrm{vol}(V)/D$. This removes edges with total capacity at most a $O({\log }^2\mathrm{vol}(V)/D)$-fraction of the total capacity. In the remaining graph each strongly connected component is a $\varphi$-expander and thus, by Lemma 5, has diameter at most $O({\varphi }^{-1}\log \mathrm{vol}(V))=O(D)$ (by choosing the constants appropriately, this bound can be adjusted to $\le D$). Finally, Lemma 3 turns this into an LDD with loss $O({\log }^2\mathrm{vol}(V))=O({\log }^{2}n)$.

Unfortunately, both log-factors in the Expander Decomposition (fraction of the cut capacity and diameter) are tight. Nevertheless, with some innovation we manage to bypass these bounds and improve the $O({\log }^{2}n)$ loss. To this end we propose a refined notion of expanders called lopsided expanders.

The notion of $\varphi$-sparsity defined above is oblivious to the ratio between $\mathrm{vol}(V)$ and $\mathrm{minvol}(U)$. For example, two cuts $U$ and $W$ can have the same sparsity, even though $\mathrm{vol}(U)\gg \mathrm{vol}(\overline{U})$ while $\mathrm{vol}(W)\approx \mathrm{vol}(\overline{W})$. It turns out that this leaves some unused potential, and that we should incentivize cutting cuts with large volume on both sides compared to more lopsided cuts with large volume only on one side.

Formally, we define $\psi$-lopsided sparsity of a cut $U$ as

where we include the ratio $\frac{\mathrm{vol}(V)}{\mathrm{minvol}(U)}$ in the denominator. Since $\mathrm{vol}(V)>\mathrm{minvol}(U)$, a cut can only have smaller lopsided sparsity than regular sparsity, so a graph with no sparse cuts may still have lopsided sparse cuts. A $\psi$-lopsided expander is defined as a graph with no $\psi$-lopsided sparse cuts, and can be thought of as a subclass of expanders which in addition to having no sparse cuts also has no cuts that are both sufficiently lopsided and sufficiently sparse.

The lopsided expander decomposition is otherwise identical to the standard expander decomposition defined previously, except that every strongly connected component is required to be a $\psi$-lopsided expander instead of a $\varphi$-expander. Our Lopsided Expander Decomposition has the same global “total capacity cut” guarantee as the standard expander decomposition, as stated in the following lemma coupled with a proof sketch.

It can be quickly verified that implementing the Multiplicative Weights Update method from Lemma 3 is not a problem algorithmically, and requires $O(R\cdot T)$ time, where $R=O(\log |E|\cdot D/L)$ and $T$ is the time required by the cost-minimizer. Hence, only computing the Lopsided Expander Decomposition could be costly. Since this is a strictly stronger definition that the standard Expander Decomposition, at first glance it appears hopeless that we could achieve a simple algorithm that avoids the cut-matching games machinery. Luckily, we find yet another simple insight that allows us to find a simple and intuitive algorithm after all: While it may generally be hard to find a sparse cut (even NP-hard!), in our case we only ever need to find a sparse cut in a graph with diameter more than $D$. Indeed, if the graph has already diameter at most $D$, we can stop immediately (recall that we ultimately only care about the diameter and not the expander guarantee). One way to view the algorithm is that we construct a truncated $\psi$-lopsided expander decomposition, where we terminate prematurely if the diameter is small.

Fueled by this insight, consider the following two-phase process for computing a (truncated) $\psi$-lopsided expander decomposition:

• $\mathrm{■}$

  Phase (I): We repeatedly take an arbitrary node $v$ and grow a ball around $v$ in the hope of finding a $\psi$-lopsided sparse cut. By choosing $\psi =\mathrm{\Theta }(\log \log \mathrm{vol}(V)/D)$ we can guarantee two possible outcomes:

  1. (a)

     We find a sparse cut after, say, radius $\frac{D}{4}$, in which case we cut the edges crossing the cut and recur on both sides (as in the Lopsided Expander Decomposition).

  2. (b)

     The problematic case happens: the volume of the ball reaches $\frac{3}{4}\cdot \mathrm{vol}(V)$. In this case we have spent linear time but made no progress in splitting off the graph, so we remember $v$ and move to Phase (II).

• $\mathrm{■}$

  Phase (II): We compute a buffer zone around $v$, which consists of all nodes with distance $\frac{D}{2}$ to and from $v$. We repeatedly take an arbitrary node $u$ from outside this buffer zone and grow a ball around $u$ in the hope of finding a $\psi$-lopsided sparse cut. Because we know that the $\frac{D}{4}$-radius ball around $v$ contains most of the volume of the graph, and node $u$ is picked outside of the $\frac{D}{2}$-radius buffer zone, we can prove (using similar techniques to the proof sketch of Lemma 7) that we will always find a $\psi$-lopsided sparse cut $U$ around $u$. Upon finding it, we cut the edges crossing the cut $(U,\overline{U})$ and start Phase (I) for the graph induced by nodes in $U$, while continuing Phase (II) in graph $G\setminus U$.

  When eventually there are no nodes left outside the buffer zone, we stop, since the remaining graph has diameter $\le D$.

The correctness of the procedure above is straightforward to show: we are essentially constructing a $\psi$-lopsided expander decomposition from Lemma 6, but terminating prematurely if the diameter is small. Hence, the total capacity of the cut edges is at most the total capacity of the cut edges in a “complete” $\psi$-lopsided expander, which is a $O(\log \mathrm{vol}(V)\log \log \mathrm{vol}(V)/D)$-fraction of the total capacity. The diameter guarantee follows directly from the stopping condition. By plugging this procedure into the algorithmic version of Lemma 3 we arrive at an LDD with loss $O(\log \mathrm{vol}(V)\log \log \mathrm{vol}(V))=O(\log n\log \log n)$ in time $\tilde{O}(m\text{poly}(D))$, completing the proof sketch of Theorem 8.