Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs

In this work, we only consider undirected graphs $G=(V,E)$ unless specifically mentioned otherwise. We further assume some basic familiarity with graph theory. For an introduction, we refer to standard textbooks, e.g., [21]. Throughout this work, we denote the distance between a node $v\in V$ and a set $S\subset V$ as $d(v,S)$. This distance is defined as the (weighted) length of the shortest path between $v$ and the node $w\in S$ closest to $v$. If we consider the distance w.r.t. to a subgraph $H\subset G$, we write $d_H(\cdot ,\cdot )$. Further for a subset $S\subseteq V$, a subgraph $H\subseteq G$, and a distance $\delta$, we define $B_H(S,\delta )=\{v\in V\mid d_H(v,S)\le \delta \}$ to be the so-called ball that contains all nodes in distance (at most) $\delta$ to any node in $G$. Again, for $H=G$, we omit the subscript.

In this work, we present algorithms that can be implemented in several different models of computation for parallel and distributed systems by reducing our algorithms to (approximate) shortest-path computations. Notably, we can derive algorithms for the $\mathrm{𝖢𝖮𝖭𝖦𝖤𝖲𝖳}$ and the $\mathrm{𝖯𝖱𝖠𝖬}$ models, which are the de facto standard models for distributed and parallel computing, respectively.

$\mathrm{𝖯𝖱𝖠𝖬}$: In the $\mathrm{𝖯𝖱𝖠𝖬}$ model, we assume computations are executed on a machine with $p$ processors. The processes work over a set of shared memory cells $M$. The input graph $G$ is stored in these cells. In a single step of computation, they can read and write from each cell in an atomic operation. If more than one processor writes in a cell, an arbitrary processor succeeds, i.e., we consider a CRCW $\mathrm{𝖯𝖱𝖠𝖬}$. The work of a $\mathrm{𝖯𝖱𝖠𝖬}$ algorithm is the total number of primitive read or write operations that the processors perform. Further, the depth is the length of the longest series of operations that have to be performed sequentially.

$\mathrm{𝖢𝖮𝖭𝖦𝖤𝖲𝖳}$: In the $\mathrm{𝖢𝖮𝖭𝖦𝖤𝖲𝖳}$ model [52], we consider a static graph $G=(V,E)$. Each node has a unique identifier. We assume these identifiers consist of $O(\log n)$ bits, i.e., they are picked from interval $[1,\mathrm{\dots },n^c]$ for some $c\in \mathrm{\Theta }(1)$. Time proceeds in synchronous rounds. In each round, nodes receive all messages sent in the previous round; they perform (unlimited) computation based on their internal states and the messages they have received so far. Finally, a node $v\in V$ may send a distinct message of size $O(\log n)$ to each neighbor in $G$. Thus, a message may contain a node’s identifier and a few more bits of information.

$\mathrm{𝖧𝖸𝖡𝖱𝖨𝖣}$: In addition to these two classic models of computation, we will also use the recently established $\mathrm{𝖧𝖸𝖡𝖱𝖨𝖣}$ model. The $\mathrm{𝖧𝖸𝖡𝖱𝖨𝖣}$ model was introduced in [7] as a means to study distributed systems that leverage multiple communication modes. Just as in $\mathrm{𝖢𝖮𝖭𝖦𝖤𝖲𝖳}$, we assume synchronous rounds. In the $\mathrm{𝖧𝖸𝖡𝖱𝖨𝖣}$ model, a node can send a message to all its neighbors in $G$ in the so-called local mode and also $O(\log n)$ nodes of its choice (as long as no node receives more than $O(\log n)$ messages) in the so-called global mode. One typically parameterizes the size of the messages in the local mode. For a discussion of this model, we refer the interested reader to [7, 57].
Rather than exploiting these models’ intricacies in bespoke algorithms, we reduce our algorithms to $\tilde{O}(1)$ applications of a $(1+ϵ)$-approximate shortest path algorithm with $ϵ\in O\left(1/{\log }^{2}n\right)$ and some simple aggregations on subsets of the input graph. To be precise, our algorithms are based on approximate set-source shortest paths (SetSSP) and so-called minor aggregations. In the remainder of this section, we will clarify what exactly these operations do and how efficiently they can be implemented in the $\mathrm{𝖢𝖮𝖭𝖦𝖤𝖲𝖳}$, the $\mathrm{𝖯𝖱𝖠𝖬}$, and the $\mathrm{𝖧𝖸𝖡𝖱𝖨𝖣}$ model.

First, we formalize the class of approximate SetSSP algorithms. For our algorithms, we must be able to compute the shortest paths to a subset of nodes and also to virtual nodes that may not be part of the original input graphs. We define this problem as follows:

Note that, if we can compute SetSSP on a graph $G$ in $\tau$ time/depth, we can also compute it on any set of disjoint subgraphs of $G$ in $\tau$ time/depth. To be precise, let $C_1,\mathrm{\dots },C_N$ with $C_i=(V_i,E_i)$ be a set of disjoint subgraphs of $G$ and let $S_1,\mathrm{\dots },S_N$ with $S_i\subset V_i$ be subsets of nodes from each $C_i$. Suppose, we want to compute an SetSSP from each $S_i$ in $C_i$. To this end, we simply assign a prohibitively high length to an edge between two subgraphs $C_i\ne C_j$. Then, we compute a SetSSP from $𝒮=\{S_1,\mathrm{\dots },S_N\}$ that results in a tree $T$. Due to their length, no (approximate) shortest path will ever contain an edge between subgraphs and so, the closest node to any node in $C_i$ must be from $S_i$. Thus, the tree restricted to $C_i$ is an approximate shortest path tree for $S_i$.

Our second building block are so-called minor aggregations, which were first introduced in [35, 36]. Consider a network $G=(V,E)$ and a (possibly adversarial) partition of vertices into disjoint subsets $V_1,V_2,\mathrm{\dots },V_N\subset V$, each of which induces a connected subgraph $G[V_i]$. We will call these subsets minors. Further, let each node $v\in V$ have private input $x_v$ of length $\tilde{O}(1)$, i.e., a value that can be sent along an edge in $\tilde{O}(1)$ rounds. Finally, we are given an aggregation function $⨂$ like $\text{SUM},\text{MIN},\text{AVG},\mathrm{\dots }$, which we want to compute in each part. Then a minor aggregation computes these functions in all minors $G[V_i]$. Note that the diameter of these minors might be (much) larger than the diameter of $G$. Therefore, the corresponding algorithm has to use edges outside of each minor to be efficient.

Both approximate shortest paths and minor aggregation can be efficiently implemented in arbitrary and restricted graphs in all of our models. Note that we are mainly interested in algorithms that require $\tilde{O}(1)$ aggregations and $(1+ϵ)$-approximate SetSSP computations with $ϵ\in \mathrm{\Omega }(1/{\log }^{c}n)$ as these algorithms can then be efficiently implemented in all three models. Note that efficient means different things in different models. While in the $\mathrm{𝖯𝖱𝖠𝖬}$, we hope for a polylogarithmic depth using a linear number of processors and in $\mathrm{𝖧𝖸𝖡𝖱𝖨𝖣}$ we aim for polylogarithmic runtime, we have to manage our expectations for $\mathrm{𝖢𝖮𝖭𝖦𝖤𝖲𝖳}$. In the $\mathrm{𝖢𝖮𝖭𝖦𝖤𝖲𝖳}$ model, the best we can hope for is $O(\text{HD})$, where HD denotes the length of the longest shortest path between two nodes if we ignore the weights, the so-called hop diameter. The hop-diameter is a natural lower bound for most global problems in $\mathrm{𝖢𝖮𝖭𝖦𝖤𝖲𝖳}$ as it describes the precise time in which a message starting from a node $v\in V$ can (theoretically) reach every node in the network. While this can be up to $n$, it may be much smaller in many practical graphs.

To be precise, it holds:

For general graphs, the bounds for approximate SetSSP in $\mathrm{𝖢𝖮𝖭𝖦𝖤𝖲𝖳}$ and $\mathrm{𝖯𝖱𝖠𝖬}$ follow from a recent breakthrough result [56]. Similarly, the runtimes for minor aggregation in $\mathrm{𝖢𝖮𝖭𝖦𝖤𝖲𝖳}$ and $\mathrm{𝖯𝖱𝖠𝖬}$ are given in [41] and [56], respectively. Finally, [57] showed the bounds for both SetSSP and minor aggregation in the $\mathrm{𝖧𝖸𝖡𝖱𝖨𝖣}$ model. For the runtime on $k$-path separable graphs in $\mathrm{𝖢𝖮𝖭𝖦𝖤𝖲𝖳}$, we use that $k$-path separable graphs exclude $K_{4k+1}$ as minor [22]. If the graph excludes a fixed clique minor $K_r$, the runtime of a minor aggregation is $\tilde{O}(r\cdot \text{HD})$ [37] and $(1+ϵ)$-approximate SetSSP can be solved in $\tilde{O}({ϵ}^{-2}\cdot r\cdot \text{HD})$ [56]. Note that for $\mathrm{𝖢𝖮𝖭𝖦𝖤𝖲𝖳}$, all these bounds are optimal as neither SetSSP nor the aggregation can be computed faster [41].

In the following, we give a formal statement of our contributions. First, we show that we can achieve the (asymptotically) best possible quality of $O(\log n)$ for general through approximate SetSSP and minor aggregation. Our first main theorem is the following.

By Theorem 4, this implies that the algorithm can, w.h.p., be implemented in $\tilde{O}(\text{HD}+\sqrt{n})$ time in $\mathrm{𝖢𝖮𝖭𝖦𝖤𝖲𝖳}$, and $\tilde{O}(1)$ depth in the $\mathrm{𝖯𝖱𝖠𝖬}$ and $\tilde{O}(1)$ time in $\mathrm{𝖧𝖸𝖡𝖱𝖨𝖣}$. Thus, our algorithm is currently the best randomized LDD construction in $\mathrm{𝖢𝖮𝖭𝖦𝖤𝖲𝖳}$ for general weighted graphs. It has same runtime as [55] and [13], creates clusters of strong diameter, and has (asymptotically) optimal quality of $O(\log n)$. We achieve this improvement through a more fine-grained analysis of the well-known exponential-delay clustering first used by Miller et al. [50] that was already used by Becker, Lenzen, and Emek in [13]. In fact, we only present a little addition to their existing algorithm to ensure the strong diameter.

Second, for $k$-path separable graphs with $k\in \tilde{O}(1)$, we present an algorithm with almost exponentially better quality. More precisely, our second main theorem is the following.

Thus, by the same reasoning as above, the algorithm can, w.h.p., be implemented in $\tilde{O}(\text{HD})$ time in $\mathrm{𝖢𝖮𝖭𝖦𝖤𝖲𝖳}$, and $\tilde{O}(1)$ depth in the $\mathrm{𝖯𝖱𝖠𝖬}$ and $\tilde{O}(1)$ time in $\mathrm{𝖧𝖸𝖡𝖱𝖨𝖣}$.

Our main technical novelty for proving Theorem 6 is a weaker form of a path separator that can be constructed without computing an embedding of $G$. Prior algorithms for $k$-path separable graphs, e.g. [2], often employ a so-called shortest path decomposition where we recursively compute $k$-path separators until the graph is empty. However, computing these separators requires precomputing a complex embedding, which we cannot afford in a distributed or parallel setting. Instead, we take a different approach to completely avoid the (potentially expensive) computation of an embedding. We show that by sampling approximate shortest paths (in a certain way), we can obtain what we will call a weak $𝒟$-separator. A weak $𝒟$-separator $S^{\prime }$ only ensures that in the graph $G\setminus S$, all nodes have at most a constant fraction of nodes in distance $𝒟$. In particular, in contrast to a classical separator, the graph $G\setminus S^{\prime }$ might still be connected. We strongly remark that, in considering weak separators, we sacrifice some of the useful properties of a traditional seperator. Nevertheless, this only results in some additional polylogarithmic factors in the runtime of our applications.

In this section, we discuss the natural question of why we consider LDD’s in the first place. Simply put, LDD’s are part of an algorithm designer’s toolkit for developing efficient divide-and-conquer algorithms, as they offer a generic way to decompose a given graph. As such, creating LDD’s with low edge-cutting probability plays a significant role in numerous algorithmic applications. In the following, we present a comprehensive list of applications (which we do not claim to be complete):

In this section, we present some related decomposition schemes. We focus on the $\mathrm{𝖢𝖮𝖭𝖦𝖤𝖲𝖳}$ model as it provides the greatest variety of decomposition schemes. We present a compact overview in Table 1.

Despite the vast number of applications for LDD’s on weighted graphs, research on LDD’s in a distributed setting has mostly focused on the unweighted case, producing many efficient algorithms in this regime. Two notable exceptions, however, explicitly consider weighted graphs and are closely related to our results: The work of Becker, Emek, and Lenzen [13] creates LDD’s of quality $O(\log n)$ with weak diameter⁴⁴4Actually, [13] proves a stronger property of the diameter. Although the diameter is weak, the number of nodes outside of a cluster that are part of the shortest path between two nodes of a cluster is limited. For many applications, this is sufficient and just as good as a strong diameter. for general graphs. We note that $O(\log n)$ is the best quality we can hope for in an LDD due to a result by Bartal [8]. The algorithm requires $\tilde{O}(\text{HD}+\sqrt{n})$ time in the $\mathrm{𝖢𝖮𝖭𝖦𝖤𝖲𝖳}$ model, which is optimal as each distributed LDD construction in a weighted graph requires $\mathrm{\Omega }(\text{HD}+\sqrt{n})$ time [40] as we can derive approximate shortest paths from it. Just as our algorithm, [13] consists of $\tilde{O}(1)$ $(1+ϵ)$-approximate SetSSP computations with $ϵ\in O\left(1/{\log }^{2}n\right)$. Further, [55], makes two significant improvements compared to [13]. They present a decomposition with strong diameter (instead of weak), and their construction is deterministic (instead of randomized). Here, they do not bound the probability that a specific edge of length $\mathrm{\ell }$ is cut, but instead – since the algorithm is deterministic – count the overall number of edges of length $\mathrm{\ell }$ that are cut. We say that a deterministic decomposition has quality $\alpha$, if the number of edges of length $\mathrm{\ell }$ with endpoint in different clusters is bound by $m\cdot \frac{\alpha \cdot \mathrm{\ell }}{𝒟}$. Note that $m\cdot \frac{\alpha \cdot \mathrm{\ell }}{𝒟}$ is exactly the expected number of cut edges in a probabilistic LDD of quality $\alpha$. Thus, with constant probability, the probabilistic version roughly cuts the same number of edges. However, without further information about the specific random choices made by the corresponding algorithm, a probabilistic LDD could cut many more edges. While this can be mitigated with standard probability amplification techniques, i.e., executing the algorithm $O(\log n)$ times and picking the iteration that cuts the fewest edges, a deterministic LDD does not have this problem in the first place. In a deterministic LDD, we have the guarantee that no matter what happens in the execution of the algorithm, less than $m\cdot \frac{\alpha \cdot \mathrm{\ell }}{𝒟}$ edges of length $\mathrm{\ell }$ are cut. This makes these decompositions very useful when we do not have the time or resources for $O(\log n)$ repetitions. A typical example is distributed algorithms for local problems, where we aim for sublogarithmic runtimes. That being said, they have a slightly worse quality of only $O({\log }^{3}n)$. Again, the algorithm consists of $\tilde{O}(1)$ $(1+ϵ)$-approximate SetSSP computations with $ϵ\in O\left(1/{\log }^{2}n\right)$.

For restricted graphs like planar, bounded treewidth, or minor-free graphs, we are unaware of a distributed/parallel algorithm explicitly designed for weighted graphs. The research [16, 17, 29, 34, 47, 19] in the $\mathrm{𝖢𝖮𝖭𝖦𝖤𝖲𝖳}$ model focused on so-called network decompositions for unweighted graphs that enable fast algorithms for local problems like MIS, Coloring, or Matching. In principle, these algorithms could also be applied to weighted graphs and produce LDD’s. However, their runtime depends on the diameter $𝒟$ of the resulting clusters, which might be much larger than the hop diameter (or even $n$) if the graph is weighted. We further remark that some authors use slightly different notations when describing LDD’s. While our definition above focuses on the clusters’ diameter, some works emphasize the number of cut edges. That is, they define it as a decomposition that cuts $ϵ\cdot m$ edges and creates a cluster of diameter $𝒟:=O({ϵ}^{-1})$. The quality is then described by the blowup in the diameter. Notably, Chang and Su [17] show that a low-diameter decomposition with $𝒟=O(r{ϵ}^{-1})$ can be computed in ${ϵ}^{-O(1)}{\log }^{O(1)}n$ rounds with high probability and ${ϵ}^{-O(1)}{2}^{O(\sqrt{\log n\log \log n})}$ rounds deterministically in the $\mathrm{𝖢𝖮𝖭𝖦𝖤𝖲𝖳}$ model for any $K_r$-free graph. Chang [16] later improved the deterministic runtime to $O(𝒟{\log }^{\ast }n+{𝒟}^5)$. In particular, if we translate this to our notion of quality, Chang [16] for unweighted graphs that present LDD’s in $K_r$-free graphs with quality $O(r)$ in the $\mathrm{𝖢𝖮𝖭𝖦𝖤𝖲𝖳}$ model. Therefore, our algorithm has worse a worse quality of $O(\log \log n)$ but is faster for large diameters $𝒟$, which arguably trades off its worse cutting probability. Also note that our techniques are entirely different from those of [16]. We elaborate more on this in the full version [24].

The main part of the paper is structured as follows: In Section 2 we present the algorithm behind Theorem 5. In doing so, we also present several useful intermediate results we reuse later. Then, in Section 3 we present our novel technique to compute weak separators. In Section 4, we combine our insights into clustering algorithms from Section 2 and findings on the construction of separators from Section 3 to develop the algorithm behind Theorem 6.

We begin with a crucial technical theorem that will build the foundation of most of our results. A key component in this construction is the use of truncated exponential variables. In particular, we will consider exponentially distributed random variables truncated to the $[0,1]$-interval. Loosely speaking, a variable is truncated by resampling it until the outcome is in the desired interval. In the following, we will always talk about variables that are truncated to the $[0,1]$-interval when we talk about truncated variables. The density function for a truncated exponential distribution with parameter $\lambda >1$ is defined as follows:

The truncated exponential distribution is a useful tool for decompositions that has been extensively used in the past [4, 32, 51]. Using a truncated exponential distribution and $(1+ϵ)$-approximate SetSSP computations, we prove a helpful auxiliary result, namely:

Technically, this algorithm is a generalization of the algorithm in [32] that is based on exact shortest path computations. This algorithm is itself derived from [50]. Our algorithm replaces all these exact computations through $(1+ϵ)$-approximate calculations. The main analytical challenge is carrying the resulting error $ϵ$ through the analysis to obtain the bounds in the theorem. The same approach was already used by Becker, Lenzen, and Emek [13]. However, our analysis is more fine-grained w.r.t. to the impact of the approximation parameter $ϵ$.

In the following, we give the high-level idea behind the construction. An intuitive way to think about the clustering process from [32, 50] is as follows: Each center $x$ draws value ${\delta }_x\sim 𝒟\cdot \mathrm{𝖳𝖾𝗑𝗉}(2+2\log \tau )$ and wakes up at time $𝒟-{\delta }_x$. Then, it begins to broadcast its identifier. The spread of all centers is done in the same unit tempo. A node $v$ joins the cluster of the first identifier that reaches it, breaking ties consistently. If we had $O(𝒟)$ time, we could indeed implement it exactly like this. However, this approach is infeasible for a general $𝒟\in \tilde{\mathrm{\Omega }}(1)$ in weighted graphs as $𝒟$ may be arbitrarily large. Instead, we will model this intuition using a virtual super source $s$ and shortest path computations. For each center $x\in 𝒳$, we independently draw a value ${\delta }_x\sim 𝒟\cdot \mathrm{𝖳𝖾𝗑𝗉}(2+2\log \tau )$ from the truncated exponential distribution with parameter $2+2\log (\tau )$. We assume that $\tau$ (or some upper bound thereof) is known to each node. Then, we add a virtual source $s$ with a weighted virtual edge $(s,x)$ to each center $x\in 𝒳$ with weight $w_x:=(𝒟-{\delta }_x)$. Then, we compute a $(1+ϵ)$-approximate SetSSP from $s$ with $ϵ\le \frac{1}{40\log \tau }$. Any node joins the cluster of the last center on its (approximate) shortest path to $s$.

With exact shortest paths, this construction would preserve the intuition. Any node whose shortest path to $s$ contains center $x$ as its last center on the path to $s$ would have been reached by $x$’s broadcast first. The statement is not that simple with approximate distances as the approximation may introduce a detour, so the center that minimizes $(𝒟-{\delta }_x)+d(x,v)$ may not actually cluster a node $v\in V$. In particular, two endpoints of a short edge $\{v,w\}$ may end up in different clusters although the same center minimizes the distance to both. The approximation error for $v$ could be large, while for $w$, it is very low, which can cause undesired behavior. The nodes will only be added to the same cluster, if its center’s head start (which is determined by the random distance to the source) is large enough to compensate for the approximation errors. This, however, depends on the approximation and not an the length of the edge we consider. Nevertheless, if the error $ϵ$ is small enough, we get similar clustering guarantees that are good enough for our purposes. In particular, if the difference in distance between the two closest centers is larger than $O(ϵ𝒟)$, the clustering behaves very similar to its counterpart with exact distances. In our analysis, we show this by carefully carrying the approximation error through the analysis. We do not introduce any fundamental new techniques, but simply carry the approximation error all the way through the analysis of the corresponding clustering process with exact distances presented in [32].

In addition to Theorem 8 itself, this also allows us to observe the positive correlation between nodes that are on the shortest path to some cluster center. This closer look also allows us to prove the following technical fact about the pseudo-padded decompositions:

This lemma states that if a single node $v\in V$ is padded, all nodes on a short path to its cluster center are likely padded as well. While this initially sounds very technical, it roughly translates to the following: Consider a clustering $𝒦=K_1,\mathrm{\dots },K_N$. Then for a suitably chosen $\rho ≔\frac{𝒟}{c\cdot \log \tau }$, in each cluster ${𝒦}_i=(V_i,E_i)$ there is a constant fraction of nodes $V_i^{\prime }\subseteq V_i$ in the distance $\rho$ to their closest node in a neighboring cluster $K_j\ne K_i$ and for any two $v,w\in V_i^{\prime }$ there is a path of length $6𝒟$ (via the cluster center) that only consists of nodes in $V_i^{\prime }$. This insight will be crucial for our next algorithm. A more detailed description and the full proof of both lemmas can be found in the full version [24].

In this section, we present a generic algorithm that creates an LDC with strong diameter of quality $(O(\log \tau ),1/2)$ if the number of nodes that can be centers of clusters has been sufficiently sparsed out. In particular, we suppose that each node can only be in one of $\tau$ clusters. For this case, we show that it holds:

The algorithm uses the so-called blurry ball growing (BBG) technique. This is perhaps the key technical result that Becker, Emek, and Lenzen introduced in [13]. It provides us with the following guarantees:

This technique allows us to create clusters with a low probability of cutting an edge while only having access to approximate shortest paths. Note that in [55] the dependency on $ϵ$ was improved to $O\left(1/\log n\right)$. The paper also presents a deterministic version of blurry ball growing. However, we will only use the probabilistic version introduced above.

Given this definition, we now give an overview of the algorithm that creates an LDC: In the following, define $\rho ≔\frac{𝒟}{c\cdot \log \tau }$ where $c$ is the constant from Lemma 9. The algorithm first computes a pseudo-padded decomposition $𝒦=K_1,\mathrm{\dots },K_N$ of strong diameter $8𝒟$ using the algorithm of Theorem 8. To do this, we choose the given set $𝒳$ of marked nodes as the set of cluster centers.

The following steps are executed in each cluster $K_i$ in parallel. Within each cluster $K_i$, we determine a so-called inner cluster $K_i^{\prime }\subseteq K_i$ of strong diameter $6𝒟$ where each node $v\in V_i^{\prime }$ has distance (at least) ${\rho }^{\prime }≔\rho /2$ to the closest node in different cluster $K_j\ne K_i$. These inner clusters can be determined via two (approximate) SetSSP computations: First, all nodes calculate the $2$-approximate distance to the closest node in a different cluster. To do this, we first create a virtual supersource $s$, and all nodes $v\in K_i$ with an edge to a node $w\in K_j$ create a virtual edge of length ${\mathrm{\ell }}_{(v,w)}$ to $s$. If they have several such neighbors, they choose the shortest edge. Then, we perform a $2$-approximate SetSSP from $s$ on the resulting virtual graph that consists of all edges within a cluster and the virtual edges to $s$. In other words, the edges $\{v,w\}$ between clusters are not considered.

We then mark all nodes where this $2$-approximate distance exceeds $2{\rho }^{\prime }$ as active nodes. Next, we consider the graph $G^{\prime }$ induced by the active nodes. Using a $(1+\frac{1}{40\log \tau })$-approximate SetSSP calculation, the active nodes compute if they have a path of length at most $3𝒟$ to their cluster center in $G^{\prime }$. If so, they add themselves to the inner cluster $K_i^{\prime }$ of $K_i$. Recall that their exact distance to the next cluster is at least ${\rho }^{\prime }$ as the paths are $2$-approximate. Further, for any two nodes $v,w\in K_i^{\prime }$ there is a path of length at most $6𝒟$ via the cluster center and so the inner cluster has a strong diameter of $6𝒟$. Thus, this procedure always results in an inner cluster $K_i^{\prime }$ with the desired properties. In the third and final stage of the algorithm, the actual clusters are computed. To this end, the inner clusters ${𝒦}^{\prime }≔{\bigcup }_{i=1}^N{K}_i^{\prime }$ are used as the input set to the BBG procedure from Lemma 11. In particular, we choose the parameter for the BBG to be ${\rho }^{\prime \prime }≔{\rho }^{\prime }/2$ and compute the superset $S({𝒦}^{\prime })≔\mathrm{𝖻𝗅𝗎𝗋}({𝒦}^{\prime },{\rho }^{\prime \prime })$. Now define final clustering $𝒞=C_1,\mathrm{\dots },C_N$ where $C_i≔K_i\cap S({𝒦}^{\prime })$. In other words, the cluster $C_i$ contains the inner cluster $K_i^{\prime }$ and all nodes from $K_i$ added by the BBG process.

The resulting clustering fulfills all three properties required by Theorem 10. For the cutting probability, note that the distance from an inner cluster to a different cluster is ${\rho }^{\prime }$, and BBG only adds nodes in distance smaller than $2{\rho }^{\prime \prime }={\rho }^{\prime }$. Thus, all edges with an endpoint in cluster $K_i$ are only cut by the blurring process and not by the initial pseudo-padded decomposition. Thus, the choice of ${\rho }^{\prime \prime }$ implies that edges are cut with correct probability of $O(\mathrm{\ell }/{\rho }^{\prime \prime })=O(\frac{\mathrm{\ell }\cdot \log \tau }{𝒟})$ by Lemma 11. The (strong) diameter of the cluster is at most $8𝒟$ as each node is in the distance at most $\rho \le 𝒟$ to a node from an inner cluster, and all nodes in an inner cluster are in the distance $6𝒟$ to one another. Therefore, it only remains to show that a nodes is clustered with prob. $1/2$. We can prove this via Lemma 9. For all nodes $v\in V$ the following holds with probability $1/2$: Node $v\in K_i$ and all nodes on the path $P_v$ of length $2(1+\frac{1}{40\log \tau })𝒟$ to its cluster center $x_i$ are in distance at least $\rho$ to the closest node in a different cluster. Therefore, all these nodes will mark themselves active. As the $2$-approximate SetSSP only overestimates, these nodes compute a distance more than $\rho =2{\rho }^{\prime }$, which causes them to be active. Moreover, this implies that the path $P_v$ is fully contained in the graph $G^{\prime }$ induced by active nodes. As the path $P_v$ is of length $2(1+\frac{1}{40\log \tau })𝒟$ and ends in the cluster center $x_i$, the $(1+\frac{1}{40\log \tau })$-approximate SetSSP computation will find a path of length at most $(1+\frac{1}{40\log \tau })2(1+\frac{1}{40\log \tau })𝒟\le 3𝒟$ in $G^{\prime }$. Therefore, with a probability of at least $1/2$, node $v$ and all nodes on the path to the cluster center will be added to the inner cluster $K_i^{\prime }$. Thus, Theorem 10 follows as half of all nodes are in an inner cluster and are therefore guaranteed to be in some cluster $C_i$. A more detailed description and the full proof can be found in the full version [24].

In this section, we show that we can create an LDD with quality $O(\log n)$ for any graph within $\tilde{O}(1)$ minor aggregations and $(1+ϵ)$-approximate SetSSP’s. Note that, at first glance, the theorem follows almost directly from Theorem 10. Choose $𝒳=V$ and ${𝒟}^{\prime }=8𝒟$ and apply the theorem to a graph $G$. We obtain a clustering with diameter ${𝒟}^{\prime }$ if each node has one node in distance ${𝒟}^{\prime }/8$ and at most $\tau$ nodes in distance ${𝒟}^{\prime }$. Clearly, for every possible choice of parameter ${𝒟}^{\prime }$, each node has at least one marked node in distance ${𝒟}^{\prime }/8$, namely itself. Further, for every possible choice of parameter ${𝒟}^{\prime }$, each node has at most $n$ marked node in distance $𝒟$ because there are only $n$ nodes in total. Thus, by choosing all nodes as centers, we obtain a clustering with quality $O(\log n)$ and a diameter we can choose freely. While the diameter and edge-cutting probability of the resulting clustering are both (asymptotically) correct, we can only guarantee that at least half of the nodes are clustered on expectation. To put it simply, we do not have a partition as required. However, we can reapply our algorithm to the graph induced by the unclustered nodes. This clusters half of the remaining nodes on expectation. Thus, by applying Markov’s inequality, a constant fraction of nodes is clustered with constant probability. It is easy to see that if we continue this for $O(\log n)$ iterations, we obtain the desired partition, w.h.p. Further, this will not significantly affect the edge-cutting probability, as each edge that is not cut will be added to a cluster with constant probability. Therefore, there cannot be too many iterations where the edge can actually be cut. Thus, applying the algorithm until all nodes are clustered intuitively produces the required LDD of quality $O(\log n)$. We formalize and prove this intuition in the following lemma.

The full proof can be found in the full version [24]. Together, Lemma 12 and Theorem 10 imply Theorem 5. Note that we state Lemma 12 more generally than needed, so we can reuse it in the next section.