1 Introduction↩︎

The graph diameter, defined as the maximum shortest-path distance between pairs of vertices, is one of the most central and widely studied graph parameters. The diameter serves as an indicator of graph complexity, and consequently many practical applications involve estimating it [1]–[4]. As computing the exact diameter is hard under fine-grained assumptions [5], much work has gone into constructing approximation algorithms [5]–[9], studying the hardness of approximating this value [7], [10]–[13] as well as studying it in specialized settings [14]–[17].

In undirected graphs, the natural distance between a pair of points \(u,v\) is the length of the shortest path between them, \(d(u,v)\). In directed graphs, however, this notion is no longer symmetric and the shortest path (or one-way) distance, from \(u\) to \(v\), \(d(u,v)\), may differ significantly from the distance in the opposite direction, \(d(v,u)\). In the context of the graph diameter, this asymmetry can lead to often unsatisfying answers, as the diameter of a graph with more than one strongly connected component is infinite under this one-way notion of distance. This in part has motivated the study of various notions of distance in directed graph, including the roundtrip distance, \(d(u,v) + d(v,u)\) [18], the max-distance \(d_{\max}(u,v)\mathrel{\vcenter{:}}= \max(d(u,v), d(v,u))\) [19] and the min-distance \(d_{\min}(u,v)\mathrel{\vcenter{:}}= \min(d(u,v), d(v,u))\) [19].

As with the standard definition of distance, computing the diameter under these various notions of distance requires \(\Omega(m^{2-\varepsilon})\) under the Strong Exponential Time Hypothesis (SETH) [5], [19] so we resort to search for approximation algorithms instead. Among these notions, the roundtrip distance and the max-distance are metrics, and therefore many algorithms for the traditional diameter extend naturally to these settings as well [5], [7], [8]. The min-distance, in contrast, is not a metric since it does not satisfy the triangle inequality. This has inspired a long line of work on approximating graph parameters in the min-distance setting, as no existing algorithms extend to this setting directly.

In this paper we study the min-distance measure, focusing in particular on the diameter of a graph under this notion, known as the min-diameter. This distance measure naturally captures real-world scenarios, such as determining the fastest way for a patient to receive care - either by traveling to a hospital or by having a doctor come to them.

In the paper that introduced the concept of min-distance, Abboud, Vassilevska W. and Wang [19] showed a simple 2-approximation to the min-diameter in near-linear² time in directed acyclic graphs (DAGs). Follow up work has obtained further results for the DAG setting [20], [21].

For general graphs, a linear-time \(2\)-approximation appears to be far beyond reach. The best known lower bound for the problem was shown by Berger, Kaufmann and Vassilevska Williams [21], where they showed any \((2-\varepsilon)\)-approximation for min-diameter requires \(\Omega(m^{2-o(1)})\) time. Initially, it was unclear whether any nontrivial approximation could be achieved in subquadratic, let alone near-linear time. In 2019, Dalirrooyfard et al. [22] gave the first approximation algorithm for the min-diameter in general graphs, establishing a tradeoff between approximation quality and runtime: for any integer \(k \geq 1\), they obtained a \((4k-1)\)-approximation in \(\tilde{\mathcal{O}}(mn^{1/(k+1)})\) time³. In particular, their result yields a \(\log n\)-approximation in near-linear time, while the best approximation factor they achieve is \(3\) in \(\tilde{O}(m\sqrt{n})\) time. It remained open whether a constant-factor approximation could be achieved in near-linear time. This question was resolved by Chechik and Zhang [23], who obtained a \(4\)-approximation to the min-diameter in near-linear time.

Following this work on the min-distance, recently Kirkpatrick and Vassilevska W. [24] introduced the notion of multimode graphs, which generalize the min-distance. A \(k\)-multimode graph \(\mathcal{G}= (V, E_1, \ldots, E_k)\) is defined as a graph with a single set of vertices and \(k\) sets of edges on the same vertex set. A shortest path is defined as the shortest path on one of the edges sets, \(d_\mathcal{G}(u,v) \mathrel{\vcenter{:}}= \min_i d_{(V, E_i)}(u,v)\). Note that if we take a directed graph \(G = (V,E)\) and denote by \(\overleftarrow{E}\) the same edges in the reverse direction, then the 2-mode distance in the 2-multimode graph \(\mathcal{G}= (V, E, \overleftarrow{E})\) is exactly the min-distance in \(G\).

The more general problem of directed 2-mode distance is strictly harder than the min-distance in some settings, such as approximating the radius, or the smallest eccentricity in the graph. While under fine grained assumptions no subquadratic approximation can exist for the directed 2-mode radius [24], there exist numerous such approximation for the min-radius [19], [22], [23]. For the case of the diameter, no strong hardness result exists to separate the problems of approximating min-diameter and directed 2-mode diameter. Nonetheless, before this work the best known approximation for 2-mode diameter running in near-linear time obtained only a factor \(n\) approximation [24]. In this paper we bring this approximation factor down significantly, closing the gap between the two problems.

1.1 Our Results↩︎

Our results in the context of current best-known algorithms are summarized in 1. Our main result is an improved approximation to min-diameter, obtaining a near-linear time 3-approximation.

This result strictly improves upon the entire tradeoff of Dalirrooyfard et al. [22] for all values of \(k\), achieving an equal or better approximation ratio with faster runtime. In addition, it improves upon the \(4\)-approximation of Chechik and Zhang [23] by reducing the approximation factor to \(3\).

Our secondary result is an extension of this theorem to multimode graphs:

This result improves upon the best previously known algorithm of Kirkpatrick and Vassilevska W. [24], bringing the approximation ratio down from \(n\) to \(3\).

To obtain our results we develop a type-classification framework which could be of independent interest to the study of algorithmic questions in the min-distance setting or other non-metric distance measures.

1.2 Technical Overview↩︎

Given a threshold \(D\), our goal is to either find a pair of vertices \((u,v)\) such that \(d_{\min}(u,v) \geq D/3\), or determine that \(\texttt{min-diam}(G)<D\). By performing a binary search over \(D\), we can identify the optimal threshold and thereby obtain a \(3\)-approximation to the min-diameter.

Starting from the full set of vertices, a natural approach, used in many previous min-diameter approximation algorithms, is to partition the set into two balanced subsets and recurse (e.g. [19]). To this end, we sample a vertex \(x\) and compute its incoming and outgoing balls of radius \(D/3\), namely \(C_1 = B^-(x, D/3)\) and \(C_2 = B^+(x, D/3)\). If it is the case that \(\texttt{min-diam}(G) \geq D\), then there exists a pair of diameter endpoints \((s,t)\) such that \(d_{\min}(s,t) \geq D\). This pair must lie entirely within either \(C_1\) or \(C_2\), since otherwise there would exist a path of length less than \(2D/3\) between them, contradicting the assumption. Consequently, by recursing on \(C_1\) and \(C_2\), we are guaranteed that at least one of the two sets contains a pair of vertices at min-distance at least \(D\).

This approach appears promising. However, recursing on these sets does not guarantee correctness: if we later find a pair of vertices with min-distance at least \(D/3\), it is unclear whether their distance was already large in the original graph or became large due to the removal of some of the vertices along the shortest path between them. To address this issue, we adopt the idea of Chechik and Zhang [23] and introduce padding vertices in the recursive calls - vertices that are not considered as potential diameter endpoints but may lie on shortest paths between such pairs.

In our setting, we include \(P_1 \mathrel{\vcenter{:}}= B^-(C_1, D/3)\) as padding for \(C_1\) and \(P_2 \mathrel{\vcenter{:}}= B^+(C_2, D/3)\) as padding for \(C_2\). We then recursively invoke the algorithm on the pairs \((C_1, P_1)\) and \((C_2, P_2)\). Computing single-source shortest paths (SSSP) from vertices in \(C_1\) using only edges induced by \(P_1\) ensures that any path of length less than \(D/3\) between two vertices in \(C_1\) is preserved. Consequently, if we find a pair \(u,v \in C_1\) such that \(d_{\min}^{G[P_1]}(u,v) \geq D/3\), then it follows that \(d_{\min}^{G}(u,v) \geq D/3\). Otherwise, either \(d_G(u,v) < D/3\) or \(d_G(v,u) < D/3\), and in both cases the corresponding shortest path is fully contained in \(P_1\).

Having addressed correctness, we now face a different issue: the recursive sets may overlap, potentially causing a rapid blow-up in the runtime. To address this problem, we introduce a parameter \(L \approx \log n\) and only recurse on \((C_1, P_1)\) and \((C_2, P_2)\) when the overlap between \(P_1\) and \(P_2\) involves fewer than \(m/L\) edges. We choose \(L\) to upper bound the recursion depth, allowing for a multiplicative \((1 + 1/L)\) increase in the number of edges at each level. Over at most \(L\) levels of recursion, this results in a total blow-up of at most \((1 + 1/L)^L = \mathcal{O}(1)\) in the number of edges. If the overlap is large, we instead handle the vertices associated with the overlap separately (see below). Since this case arises only when the overlap is large, we can argue that after at most \(L\) attempts, we will find a vertex \(x\) that yields the desired partition with small overlap.

To handle the large overlap we introduce a new concept - designating vertices into one of two types. We say that a vertex \(v\) is degenerate if its min-distance to either diameter endpoint is at least \(D/3\). In this case, running SSSP from \(v\) would already find a pair of points of the desired distance. For a non-degenerate vertex \(v\), it must hold that either both \(d(s,v) < D/3\) and \(d(t,v) < D/3\), or both \(d(v,s) < D/3\) and \(d(v,t) < D/3\). We refer to vertices satisfying the former condition as Type 1, denoting their set by \(T_1\), and those satisfying the latter as Type 2, denoting their set by \(T_2\).

Now consider two non-degenerate vertices \(u\) and \(v\) such that \(d(u,v) < D/3\). If \(u \in T_1\), then necessarily \(v \in T_1\), as otherwise the path \(s \rightsquigarrow u \rightsquigarrow v \rightsquigarrow t\) would have length less than \(D\), contradicting the choice of \(s,t\); see 1. Similarly, if \(v \in T_2\), then \(u \in T_2\). Therefore, if there exists a complete cycle of non-degenerate vertices \(u_1, u_2, \ldots, u_k\) such that \[d(u_1,u_2), \ldots, d(u_{k-1},u_k), d(u_k,u_1) < D/3,\] then all vertices \(u_1, \ldots, u_k\) must belong to the same type.

Thus, suppose we obtain a partition \((C_1, P_1), (C_2, P_2)\) with a large overlap \(W_x \mathrel{\vcenter{:}}= P_1 \cap P_2\), where \(|E[W_x]| > m/L\). Intuitively, this overlap corresponds to a large set of vertices that all share the same type. If all vertices in \(W_x\) are of Type 1, we repeatedly sample \(\Theta(\log n)\) vertices and take the intersection of their incoming \(D/3\) neighborhoods, retaining \(s\) or \(t\) if they were already present. A lemma from prior works [25], [26] ensures that, with high probability, each iteration shrinks the set by a constant factor. Consequently, after \(\Theta(\log n)\) iterations, the set becomes sufficiently small, allowing us to identify \(s\) or \(t\). An analogous procedure applies if all vertices are of Type 2, using intersections of outgoing \(D/3\) neighborhoods. If no pair of vertices with min-distance at least \(D/3\) is found, we conclude that neither \(s\) nor \(t\) lies in the overlap, and we remove the corresponding vertices from further consideration. More precisely, we consider the sets \(C_1 \cap B^+(W_x, 2D/3)\) and \(C_2 \cap B^-(W_x, 2D/3)\), whose vertices are guaranteed to share the same type as \(x\), and remove them from \(C\) if neither \(s\) nor \(t\) is found.

We now repeat the process by sampling a new vertex \(x' \in C\) and constructing the corresponding sets \(C'_1, C'_2, P'_1, P'_2\). It is again possible that the resulting overlap \(W_{x'}\) is large. However, we observe that \(W_{x'}\) must be disjoint from \(W_x\), since otherwise \(x'\) would have been removed from \(C\) in the previous iteration. This disjointness property ensures that after at most \(L\) such attempts, we obtain a vertex \(x'\) whose corresponding overlap is small, allowing us to recurse while incurring only a \((1+1/L)\) multiplicative increase in the total number of edges.

The approach outlined above has one remaining issue. While initially we may assume that any vertex from which we run SSSP is non-degenerate, since otherwise we would already be done, this assumption no longer holds after recursion. In particular, the recursion partitions vertices into a set of potential diameter endpoints \(C\) and padding vertices \(P\). While we are guaranteed that any pair of vertices in \(C\) with min-distance at least \(D/3\) is also far apart in the original graph, this guarantee does not extend to pairs of vertices in \(P\). Consequently, vertices in the overlap \(W_x\) may be degenerate, since \(W_x\) may consist entirely of padding vertices.

To address this issue, we propagate multiple layers of padding with each recursive call, namely \(P_1, \ldots, P_{L+1}\). After the first call, we can ensure that any vertex explored in \(C, P_1, \ldots, P_L\) is non-degenerate (otherwise we would have already terminated), since all paths of length less than \(D/3\) between such vertices are preserved in the final padding layer \(P_{L+1}\).

Applying the previous arguments, we can therefore identify a vertex \(x\) such that the \(L\) layers of padding constructed around it have small overlap. Upon recursing, we maintain that vertices in \(C\) together with the first \(L-1\) padding layers remain non-degenerate, and this invariant continues inductively. Although we lose one layer of padding at each level of recursion, the choice of \(L\) as an upper bound on the recursion depth ensures that, even at the final level, all paths of length less than \(D/3\) between vertices in \(C\) are preserved.

1.3 Discussion and Open Problems↩︎

In prior work on graph parameters under the min-distance measure, techniques for approximating the min-diameter have often extended to the min-radius and, more generally, to approximating all min-eccentricities. In particular, the previous best min-diameter algorithms admit matching results for min-radius: a \(3\)-approximation in \(\tilde{\mathcal{O}}(m\sqrt{n})\) time [22], and a \(4\)-approximation in near-linear time [23]. However, it is unclear whether the techniques developed in this work extend to the radius setting.

The key idea in our algorithm - the type-classification framework, admits an analogous formulation for the radius problem. Suppose \(\texttt{min-radius}(G)\leq R\), let \(c\) be a center, and consider the task of finding a vertex with min-eccentricity at most \(3R\), which we call degenerate. Every vertex \(u\) satisfies either \(d(u,c)\leq R\) or \(d(c,u)\leq R\); we refer to vertices satisfying the former as Type 1 and the latter as Type 2. The main observation is that if there exists a path of length at most \(R\) from a Type 2 vertex to a Type 1 vertex, then both vertices are degenerate. This yields structural properties analogous to those used in our min-diameter approximation algorithm.

This suggests that our techniques may extend to the radius setting. However, the key step in our algorithm - using \(L\) layers of padding to ensure that degenerate vertices in the padding yield a valid solution, does not appear to generalize.

On the other hand, our techniques do extend from the min-distance setting to the multimode setting in the case of diameter. A similar extension for radius is unlikely, as any subquadratic approximation of the directed \(2\)-mode radius is hard under fine-grained assumptions [24]. Thus, obtaining a near-linear-time \(3\)-approximation for the min-radius, and more generally improving approximations for min-eccentricities, remains an interesting open problem.

1.4 Organization↩︎

In 2 we introduce the necessary definitions and preliminary lemmas. In 3 we develop a type-classification framework, which we then use in 4 to prove 1. Finally, in 5 we extend this result to the multimode setting.

2 Preliminaries↩︎

Let \(G = (V,E)\) be a graph with \(n = |V|\) vertices and \(m = |E|\) edges. We will use \(m\) throughout the paper to refer to the number of edges in the current instance of the graph we are working with (which might be significantly smaller than the graph we started out with). When referring to the number of edges in some former graph we use \(|E|\) to avoid ambiguity.

Denote by \(d_G(u,v)\) the length of the shortest path from \(u\) to \(v\) in \(G\). We omit \(G\) from the notation when it is clear from context. Given a vertex \(u\) and value \(r\) denote by \(B^+(u,r),B^-(u,r)\) the outgoing and incoming balls of radius \(r\) around \(u\), i.e. \(B^+(u,r) \mathrel{\vcenter{:}}= \{w:d(u,w) < r\}, B^-(u,r) \mathrel{\vcenter{:}}= \{w:d(w,u) < r\}\).

Given a subset of vertices \(U\subseteq V\) define \(E[U]\) to be the edges in \(E\) with both endpoint in \(U\) and \(G[U] \mathrel{\vcenter{:}}= (U, E[U])\).

Denote by \([k]\) the set \(\{1,\ldots, k\}\). For ease of notation, when referring to cycles \(v_1, \ldots, v_k\) we abuse the notation of \({\text{mod }k}\) and say something is true for all pairs \((v_i, v_{i+1_{\text{mod }k}})\) to mean the pairs \((v_1, v_2) , \ldots, (v_{k-1}, v_k),(v_k, v_1)\).

Next, we define the two non-standard notions of distance we use throughout the paper. The min-distance between a pair of points in a directed graph \(G\) is defined as the minimum of the two directed distances between them, \(d_{\min}^G(u,v) \mathrel{\vcenter{:}}= \min(d_G(u,v), d_G(v,u))\). Again, when \(G\) is clear from context we omit it. We define the min-diameter of \(G\), or \(\texttt{min-diam}(G)\) to be the largest min-distance between a pair of points in \(G\).

A \(k\)-multimode graph \(\mathcal{G}= (V, E_1, \ldots, E_k)\) is defined by a set of vertices \(V\) and \(k\) sets of edges, \(E_i \subset V\times V\) [24]. Denote by \(G_i = (V, E_i)\) and \(d_i(u,v) = d_{G_i}(u,v)\). The \(k\)-mode distance is defined as \(d_\mathcal{G}(u,v) = \min_i d_i(u,v)\). The \(k\)-mode diameter of \(\mathcal{G}\) is defined as \(\max_{u,v\in V}d_\mathcal{G}(u,v)\). Given a subset \(U\subseteq V\) define \(\mathcal{G}[U] = (U, E_1[U], \ldots, U_k[u])\).

Lastly, we include some definitions and lemmas from prior work which we will use in our algorithms. First we define a partition of a set \(C\), introduced under different notation by Dalirrooyfard et al. [22].

The use of ID in this definition is entirely arbitrary, as when a vertex is of equal distances to \(x\) in both directions we don’t care which set it falls into. We only need this choice to be consistent, i.e. if \(x\) falls into \(C_y^+\) then \(y\) falls into \(C_x^-\).

The following is equivalent to Lemma 3.1 in [22]

Next, we introduce a lemma used in prior work on directed girth approximation. This lemma, taken from [25], is attributed to [26].

Note that by flipping the direction of all edges we get the same lemma for the symmetric case when \(S'\) is defined by \(S\cap \bigcap_{r\in R}B^+(r,p)\).

In the original statement of this lemma the condition on \(S\) is that for every \(a\in S\) there are at most \(0.2 |S|\) nodes \(b \in V\) (not \(S\)) such that \(d(a,b),d(b,a) \leq p\) (and not \(<\)), their statement also required \(p\) to be an integer. However, this original statement would be insufficient for our purposes. The original proof of [25] still works in our more restrictive setting with slight adjustments, we include it here for completeness.

3 The Type Framework↩︎

Before constructing our min-diameter approximation algorithm we begin by creating a type-classification framework. We define two different types that points can be, a way to find points of the same type and a useful property that arises from large sets of points of a single type.

Given a threshold \(D\), we would like to find a pair of points with \(d_{\min}(u,v)\geq D/3\) or determine that \(\texttt{min-diam}(G)<D\). By binary searching over \(D\) we find the best choice of \(D\) and obtain a \(3\)-approximation to the min-diameter.

Assume we are in the case that \(\texttt{min-diam}(G) \geq D\), we would like to find a pair of points of min-distance greater than \(D/3\) in some subset \(U\). Let \(s,t\) be a pair of diameter endpoints, \(d_{\min}(s,t) \geq D\) and define the type of a vertex according to \(s\) and \(t\). For the sake of readability we will not index our notations by \(s,t\) and \(D\) but it is important to emphasize that all the definitions in this section are with respect to a fixed (unknown) pair of diameter endpoints and a given threshold \(D\).

Note that if a vertex \(v\) is in neither \(T_1\) or \(T_2\) then computing SSSP from this vertex will find a min-distance \(\geq D/3\) to either \(s\) or \(t\), concluding our algorithm. We will call such points degenerate.

Clearly, running SSSP from a degenerate point will result in finding the desired approximation. We therefore assume for the rest of the algorithm that unless stated otherwise, no point from which we run SSSP is degenerate, as otherwise we would be done.

Without knowing \(s\) and \(t\), we cannot classify the type of vertices in the graph. However, using the following claim we can identify points that share the same type as one another.

In the next lemma we see the power of having a set of points of the same type, even if we don’t know which of the two types it is. More specifically, if a set contains a diameter endpoint and we have the guarantee that all points in it are either degenerate or of the same type, then we can find our desired \(3\)-approximation in linear time.

We note that the above algorithm runs in \(\tilde{O}(m)\) time regardless of whether the conditions are met. If the conditions are not met it is not guaranteed to succeed.

Combining 4 and 3 gives us the following algorithm, which will be a useful subroutine in our main min-diameter approximation algorithm.

We again note that the algorithm in the above lemma runs in \(\mathcal{O}(\ell \cdot m\cdot \text{polylog}~N)\) time even when the conditions are not met.

4 3-Approximation to Min-Diameter↩︎

We can now construct our main algorithm and prove 1. Let \(D\) be a threshold and assume again that \(\texttt{min-diam}(G)\geq D\), \(d_{\min}(s,t) \geq D\) and we would like to find a pair of points with min-distance \(\geq D/3\).

We will start with the set \(C=V\) as our set of potential diameter endpoints. At each step we will remove some points from \(C\) and then divide it into two balanced sets \(C^+, C^-\) with the guarantee that if \(s,t\) were in \(C\) at the beginning of the algorithm then either \(s,t\in C^+\) or \(s,t\in C^-\). We will then recurse on the two smaller sets.

The algorithm receives as input the depth of the recursion \(i\), a diameter estimate \(D\), the size of the original graph \(N\) and a value \(L\) that depends on the size of the original graph and remains constant as the graph gets smaller, a set of potential diameter endpoints \(C\) and up to \(L+1\) sets of padding. At depth \(i\) of the recursion we will have \(L - i+1\) padding sets, with the last \(i\) sets being empty.

Given an \(n\)-node \(m\)-edge graph \(G = (V,E)\), we set \(N=n, L = \left\lceil \log_{9/8} n \right\rceil\) and first call the algorithm on the input: \(\operatorname*{\mathbf{MinDiameter}}(i=0, D,N, L,C = V, P_1 = V, P_2 = V, \ldots, P_{L+1} = V)\). For the full pseudocode see 2.

At depth \(i\) we run all of our distance computation on \(G[P_{L-i+1}]\). For ease of notation, denote by \(m\) the number of edges in this graph, \(m = |E[P_{L-i+1}]|\).

We begin by sampling a point \(x\in C\) and compute \(C_x^+, C_x^-\) according to 1. By 1, with probability \(\geq \frac{1}{2}\) we have an \(x\) such that \(|C_x^+|,|C_x^-| \leq \frac{8}{9}|C|\). If this is not the case, we resample. After \(3\log N\) failed attempts we give up. This step succeeds with probability \(\geq 1-\frac{1}{N^3}\).

Next, we define \(L-i\) layers of padding. We take \(P_1^+\) to be the outgoing \(D/3\) neighborhood of \(C^+_x\) in \(P_1\). Similarly, we take \(P_1^-\) to be the incoming \(D/3\) neighborhood of \(C_x^-\) in \(P_1\). We repeat this \(L-i\) time: taking \(P^+_j \mathrel{\vcenter{:}}= B^+(P^+_{j-1}, D/3)\cap P_{j}, P^-_j \mathrel{\vcenter{:}}= B^-(P^-_{j-1}, D/3)\cap P_{j}\) for \(2\leq j\leq L-i\).

Now we would like to recurse. If \(W_x\mathrel{\vcenter{:}}= P_{L-i}^+\cap P_{L-i}^-\) contains \(\leq \frac{m}{L}\) edges, we call \(\operatorname*{\mathbf{MinDiameter}}\) twice. Once on \(\operatorname*{\mathbf{MinDiameter}}(i+1, D,N,L, C_x^+, P_1^+, \ldots, P_{L-i}^+, \emptyset, \ldots, \emptyset)\) and another time on \(\operatorname*{\mathbf{MinDiameter}}(i+1, D,N,L, C_x^-, P_1^-, \ldots, P_{L-i}^-, \emptyset, \ldots, \emptyset)\).

If \(s,t\in C\) then either \(s,t\in C_x^+\), in which case we will show that the first call finds a pair of points of min-distance \(\geq D/3\), or \(s,t\in C_x^-\), in which case the second call finds such a pair.

We are left to handle the case where \(|W_x| > \frac{m}{L}\). We note that by the invariants that our algorithm maintains, any pair of points in \(P_{L-i}\) (including \(C, W_x\) and padding sets in between them) of min-distance \(<D/3\) in \(G\) will have min-distance \(<D/3\) in \(G[P_{L-i+1}]\) so if we find a pair of points in this set of min-distance \(\geq D/3\) we return it and complete the algorithm.

To handle the large overlap, we isolate a set of vertices in \(C\) that are contained in a loop (in \(P_{L-i}\)) between \(x\) and \(W_x\). If \(s,t\in C\), then by 4, all these points will be either \(C\)-degenerate in \(G[P_{L-i+1}]\) (and thus we will have found a pair of far away points in \(P_{L-i}\)) or of the same type. We take our set \(A\subseteq C\) to include point in \(C^+_x\) that can reach \(W_x\) within distance \(<(L-i)D/3\) and points in \(C_x^-\) that can be reached from \(W_x\) within distance \(<(L-i)D/3\).

More precisely⁶, take \(A_{L-i-1}^+ \mathrel{\vcenter{:}}= P_{L-i-1}\cap B^-(W_x, D/3)\) and \(A_{L-i-1}^- \mathrel{\vcenter{:}}= P_{L-i-1}\cap B^+(W_x, D/3)\). For \(j = L-i-2, \ldots, 0\) define \(A_{j}^+ \mathrel{\vcenter{:}}= P_{j}\cap B^-(A_{j+1}^+, D/3)\) and \(A_j^- \mathrel{\vcenter{:}}= P_{j}\cap B^+(A_{j+1}^-, D/3)\). Finally, take \(A = A_0^+ \cup A_0^- \subseteq C\).

For each vertex in \(a\in A\) we can store a set of \(k=\mathcal{O}(L)\) points \(a=a_0, \ldots, a_{k-1} \in P_{L-i}\) such that \(x\in \{a_1, \ldots, a_k\}\) and \(d_{G[P_{L-i+1}]}(a_j, a_{j+1_{\text{mod} k}}) < D/3\) for \(j\in [k-1]\) as follows. If \(a\in A_0^+\) we take a point \(a_1\in A_1^+\) that \(a\) can reach in distance \(<D/3\), followed by points \(a_2\in A_2^+,\ldots, a_{L-i-1}\in A_{L-i-1}^+, w\in W_x\) that can each reach the next in distance \(<D/3\). We can then take \(L-i\) points in the \(L-i\) layers of padding that allow \(w\) to reach \(x\) in steps consisting of paths of length \(<D/3\), ending with \(x\). Similarly, we can find such a set for any point in \(A\cap A_0^-\).

We now have all we need to be able to run the algorithm \(\operatorname*{\mathbf{SingleType}}\) from 4, on \(P_{L-i}\), the set \(A\) and point \(x\), with \(k\) points for each vertex in \(A\), in the graph \(G[P_{L-i}]\). It runs in time \(\mathcal{O}(m L\cdot \text{polylog N})\) and if \(s\in A\) or \(t\in A\) it finds a pair of points in \(P_{L-i}\) with min-distance \(\geq D/3\) in \(G[P_{L-i+1}]\) with probability \(\geq 1-\frac{1}{N^3}\).

Thus, if \(\operatorname*{\mathbf{SingleType}}(G[P_{L-i+1}],P_{L-i}, A, x, k, D, N)\) didn’t return a pair of far apart vertices, we can assume that \(s,t\notin A\) and remove \(A\) from \(C\) (without removing the vertices from \(P_1,\ldots, P_{L-i+1}\), as they can still be used in shortest paths).

We now restart the algorithm with the smaller set \(C'\subseteq C\) - sample a new \(x'\in C'\), resample until the sets \(C_{x'}^+, C_{x'}^-\) are not too large and compute \(W_{x'}\). We note that \(W_x,W_{x'}\) are disjoint. Otherwise, if \(x'\in C_x^+\) then it would be able to reach \(W_x\) and would have been removed from \(C\). Similarly, if \(x\in C_x^-\) it would be reached from \(W_x\) and thus removed from \(C\).

Therefore, the sets \(W_x\) are disjoint over the different iterations of the algorithm. In particular, the edges contained within each set are disjoint. Since each \(|E[W_x]|\geq m/L\), after \(\leq L\) iterations we will find a vertex \(x\) with \(|E[W_x]|<m/L\) and proceed with the recursion.

Thus, our algorithm runs in time \(\tilde{\mathcal{O}}(L\cdot m) = \tilde{\mathcal{O}}(m)\) before calling the recursive step. At each level of the recursion the number of edges blows up by a factor of at most \((1 + 1/L)\). Since \(|C|\) shrinks by a factor of \(8/9\) every call, at depth \(L\) we have \(|C|\leq i^L\cdot n \leq 2\), so we do not reach any recursion depth greater than \(L\). Thus, the total number of edges at each stage of the recursion is bounded by \((1+1/L)^L\cdot |E| = \mathcal{O}(|E|)\), giving a total runtime of \(\tilde{\mathcal{O}}(|E|)\). In the following claims we formally argue correctness and runtime.

4.0.0.1 Correctness:

We argue for the correctness of the algorithm using the following two claims. First we show that at every depth of the recursion at least one call will retain a set \(C\) with a pair of points of min-distance \(\geq D\). Next, we argue that any pair of points with distance \(<D/3\) will also have distance \(<D/3\) in the recursive calls. These claims guarantee that if \(\texttt{min-diam}(G)\geq D\) then we will eventually find a pair of points of min-distance \(\geq D/3\). Since at recursion depth \(i\) all the points we consider are in \(P_{L-i}\) and we compute distances in \(G[P_{L-i+1}]\), any pair of points we return will in fact have the desired distance in \(G\).

4.0.0.2 Runtime:

Finally, we argue that our algorithm runs in \(\tilde{\mathcal{O}}(|E|)\) time. First we show that the sets \(W_x\) are in fact disjoint.

Now we can bound the number of iterations of lines [ln:samplingx]-[ln:endbigoverlap] by \(L\). The runtime of each iteration is dominated by the runtime of line [ln:callsingletypealg], \(\mathcal{O}(mL\cdot \text{polylog}N)\). Thus, lines \(\ref{ln:startmindiamalg}\)-[ln:endbigoverlap] run in time \(\mathcal{O}(L^2m\cdot \text{polylog}N)\), where recall that \(m\) denotes the number of edges in this instance, \(|E[P_{L-i+1}]|\).

Next, we bound the total number of edges across all iterations of the recursion at depth \(i\).

Now, since the runtime of each instance before its recursive call is \(\mathcal{O}(L^2m \cdot \text{polylog}N)\), we can bound the total runtime of all instances of the recursion at depth \(i\) by \[\mathcal{O}((1+1/L)^i|E|\cdot L^2\cdot \text{polylog}N).\] Next, we bound the recursion depth by \(L\).

Therefore, we have \(\leq L\) levels of recursion. At each level we have a total runtime of \(\tilde{\mathcal{O}}((1+1/L)^i|E|\cdot L^2)\) so our final runtime is bounded by \[\mathcal{O}((1+1/L)^L|E|\cdot L^3\cdot \text{polylog}N) = \tilde{\mathcal{O}}(|E|).\]

4.0.0.3 Success Probability:

Two steps of our algorithm are randomized - line [ln:resamplex] and our call to \(\operatorname*{\mathbf{SingleType}}\) in line \(\ref{ln:callsingletypealg}\). Since each succeeds with probability \(\geq 1 - \frac{1}{N^3}\), for the original size of the graph \(N=n\), and we run the algorithm \(\leq n\) times, using a union bound our algorithm succeeds with probability \(\geq 1 - \frac{1}{n}\).

5 Extension to Directed 2-Mode Diameter↩︎

In this section we show how to adapt the algorithm for computing a 3-approximation to min-diameter in linear time to the more general setting of directed 2-mode diameter. We follow the same structure of an algorithm, generalizing the notions we introduced throughout. The key observation here is that most properties we obtained from a pair of points having \(d(u,v) < D/3\) in the min-distance case we can now derive from a pair of points that have either \(d_1(u,v) < D/3\) or \(d_2(v,u) < D/3\). The main idea will be replacing outgoing (resp. incoming) balls with the union of outgoing (incoming) balls in \(G_1\) and incoming (outgoing) balls in \(G_2\) and show that the proofs generalize to this case.

For the sake of readability, we note where the proof differs from the ones given for min-diameter, instead of repeating entire proofs. Let \(\mathcal{G}= (V,E_1, E_2)\) be a directed 2-multimode graph. Again assume we are given a threshold \(D\) and if \(\texttt{diam}(\mathcal{G}) \geq D\) we would like to find a pair of points whose 2-mode distance is greater than \(D/3\).

First we generalize 1 to the multimode setting to obtain a balanced partition of the set \(C\). Intuitively, the set \(C_x^+\) consists of the vertices \(v\) such that the distance from \(x\) to \(v\) is achieved in \(G_1\) and the distance from \(v\) to \(x\) is achieved in \(G_2\) and the set \(C_x^-\) consists of the vertices for which the opposite is true. Formally, to make \(C_x^+, C_x^-\) a proper partition with our desired properties we define them as follows.

A central component to our min-diameter algorithm was the type classification. Let \(s,t\) be a pair of diameter endpoints, \(d_\mathcal{G}(s,t) \geq D\). Note that unlike in the min-diameter, these points are no longer symmetric. We say a vertex is degenerate if it has 2-mode distance \(\geq D/3\) from \(s\) or to \(t\). By similar arguments to what we’ve seen before, if a non-degenerate point \(v\) has \(d_1(s,v) < D/3\) then \(d_2(v,t) < D/3\). Otherwise, it must have \(d_2(s,v) < D/3, d_1(v,t) < D/3\). We therefore define points of Type 1 and Type 2 and degenerate as follows, and obtain the following claim.

Next we note a similar property to that used in 4. By the same arguments used previously, for two non degenerate points \(u,v\), if \(d_1(u,v) < D/3\) then \(u\in T_1\) implies \(v\in T_1\) and \(v\in T_2\) implies \(u\in T_2\). Similarly, if \(d_2(u,v) < D/3\) then \(u\in T_2\) implies \(v\in T_2\) and \(v\in T_1\) implies \(u\in T_1\). This property gives us the following generalization to 4.

The proof is a straightforward generalization using the property noted above. Next, we generalize 3

Using these generalized notions of types and degeneracy we can now obtain a generalization to 4.

We emphasize that this algorithm again runs in \(\mathcal{O}(m\cdot \text{polylog} N)\) time even when the conditions are not met, in which case it outputs null.
We can now state our generalized 3-approximation to 2-mode diameter. The algorithm receives as input the depth of the recursion \(i\), a diameter estimate \(D\), the size of the original graph \(N\), a value \(L\) that bounds the recursion depth, a set of potential diameter endpoints \(c\subseteq V\) and up to \(L+1\) sets of padding vertex.

Given an \(n\)-node 2-multimode graph \(\mathcal{G}= (V, E_1, E_2)\) we set \(N = n, L = \lceil\log _{9/8}n \rceil\) and call the algorithm on the input \(\operatorname*{\mathbf{MultiModeDiameter}}(i=0, D, N, L, C = V, P_1 = V, \ldots, P_{L+1} = V\). The full pseudocode appears in 4. Other than the different definition of \(C_x^+, C_x^-\) (4), the only difference from 2 is that when we previsouly took an outgoing ball of radius \(D/3\), we now take the union of the outgoing ball in \(G_1\) and the incoming ball in \(G_2\). Whenever we took an incoming ball of radius \(D/3\), we now take the union of an incoming ball in \(G_1\) and an outgoing ball in \(G_2\). We show that the correctness and runtime claims still hold in this generalized setting.

5.0.0.1 Correctness:

We show the analogous claims to 5 and 6 to obtain correctness.

The proof is a straightforward generalization of that 6, as at every level of padding we take a union of radius \(D/3\) balls in both \(G_1\) and \(G_2\). We obtain the same corollary, as any pair of points of distance \(<D/3\) in \(\mathcal{G}[P_{L-i+1}]\) must have a path of length \(<D/3\) between them in \(G_1\) or \(G_2\), either of which will be maintained in the recursive call.

5.0.0.2 Runtime:

The runtime and success probability analysis are nearly identical to those of 2.

References↩︎

---

1. yaelkirk@mit.edu, supported by NSF Grant No 2141064.↩︎

2. By near-linear time we mean \(O(m\operatorname{\mathrm{poly}}\log n)\).↩︎

3. We use \(\tilde{\mathcal{O}}\) to hide polylogarithmic factors in the runtime.↩︎

4. Note that \(N\) can be larger than \(|V|\) here. We will need this when we run this algorithm on small subgraphs but still want to retain high probability guarantees with respect to the size \(n\) of the original graph.↩︎

5. The set \(Q(a)\) can also be smaller than \(\ell\) by repeating vertices.↩︎

6. This is almost equivalent to taking \(A = C^+_x\cap B^-(W_x, (L-i)D/3) \cup C_x^-\cap B^+(W_x, (L-i)D/3)\), but allows us to find the points along the path more directly without the potential of introducing additive errors.↩︎