The min-distance between two vertices x, y in a directed graph G is the minimum of the one-way distances d(x, y) and d(y, x), and is written d min (x, y). This notion of distance was introduced by Abboud, Vassilevska W., and Wang [2] in their study of diameter in directed graphs. Since the standard notion of distance in directed graphs is not symmetric, [2] considered a number of symmetric distance functions: roundtrip distance, max-distance, and min-distance. The min-distance in particular, has since then been studied in a series of papers [13,15,11].
The min-distance is arguably the most natural notion of distance in directed acyclic graphs (DAGs), in which for every two vertices x, y, at most one of d(x, y), d(y, x) is finite. Min-distance is also applicable in potential real-world contexts: for example, if a patient needs to see a doctor as soon as possible, the doctor can visit the patient or vice versa.
The min-diameter of a directed graph G is the maximum min-distance between any two vertices, or max x,y∈V (G) d min (x, y). One can additionally define the bichromatic mindiameter in a graph G with vertex set V = A ⊔ B partitioned into "red" and "blue" vertices: the bichromatic min-diameter is the maximum min-distance between oppositely-colored vertices, or max a∈A,b∈B d min (a, b). These are variants on the standard notions of diameter [1,3,6,10,12,16,24] and bichromatic diameter [5,14], respectively.
One can compute min-diameter or bichromatic min-diameter -and for that matter All Pairs Shortest Paths (APSP), the shortest path distances d(x, y) for all x, y ∈ V -in an n-vertex m-edge graph in O(mn + n 2 log n) time, simply by running Dijkstra's algorithm from every vertex. In unweighted graphs, one can instead use BFS, giving an O(mn) runtime.
One might ask whether, for either min-diameter or bichromatic min-diameter, a faster algorithm exists. However, just as for standard diameter and other diameter variants that have been studied [2,14,20], the Strong Exponential Time Hypothesis (SETH) [18,9] suggests exact computation cannot be done in runtimes that are truly subquadratic, meaning O(m 2-ϵ ) for ϵ > 0. SETH is one of the main hypotheses in Fine-Grained Complexity [22], and is among the most well-established hardness hypotheses for showing conditional lower bounds. It states that for every ϵ > 0, there is an integer k ≥ 3 so that k-SAT on n variables cannot be solved in O(2 (1-ϵ)
Since exact computation is conditionally hard, we resort to finding approximations. Since min-distance does not obey the triangle inequality, approximating min-diameter is especially challenging, in comparison to standard diameter or even roundtrip diameter or max-diameter. For this reason, much of the work on min-diameter has focused on DAGs.
Abboud, Vassilevska W., and Wang [2] gave a 2-approximation for min-diameter in DAGs, running in Õ(m) time. 1 Meanwhile, they showed that if one can obtain a ( 3 2 -δ) approximation in O(m 2-ϵ ) time for min-diameter in DAGs (for ε, δ > 0), then SETH is false. The results of [2] left a gap between the conditional lower bound of 3/2 and the upper bound of 2 for O(m 2-ϵ ) time algorithms for DAGs. (The lower bound is for O((mn) 1-ϵ ) time algorithms but since the instances are sparse, this is the same as O(m 2-ϵ ) time.)
Later work by Dalirrooyfard and Kaufmann [13] showed that in dense DAGs, one can beat the mn barrier by obtaining an almost- 3 2 -approximation algorithm running in O(n 2.35 ) time. The conditional lower bound of [2] is for sparse DAGs, however, and the gap between upper and lower bounds has remained.
Our main result is to close this gap for sparse DAGs:
There is an O(m 0.713 n) time algorithm that achieves a ( 3 2 , 1 2 )-approximation for min-diameter in any m-edge, n-node unweighted DAG.
Furthermore, there is an O(m 1.426 n 0.288 ) time algorithm that achieves a 3 2 -approximation for min-diameter in any m-edge, n-node unweighted DAG.
A (c, a)-approximation for a quantity D is a quantity D ′ such that D ≤ D ′ ≤ cD + a. Similar to [13], we use hitting set and set intersection methods to certify distances. Our main new technique is to iteratively grow a central interval of vertices with convenient distance properties by checking that at least one of two neighboring vertex subsets, to its left and right, has the desired properties.
The algorithms use fast matrix multiplication. There are also combinatorial versions of the algorithms, with runtimes O(m 3/4 n) for the ( 3 2 , 1 2 )-approximation and O(m 5/4 n 1/foot_1 ) for the 3 2 -approximation. 2 These runtimess are still subquadratic for sparse graphs.
Our paper also considers the case of general directed graphs. Abboud, Vassilevska W., and Wang [2] showed that under SETH, any O(m 2-ε ) time algorithm for ε > 0 for min-diameter can achieve at best a 2-approximation. This result only held for weighted graphs.
We give the first hardness result for unweighted graphs, extending the hardness of [2]:
Under SETH, there can be no O(m 2-ε ) time (2 -δ)-approximation algorithm for the min-diameter of an unweighted directed graph with n vertices and m = n 1+o (1) edges, for ϵ, δ > 0.
Because our min-diameter approximation algorithms for DAGs obtain an approximation factor better than 2 in truly subquadratic time, this gives the first separation of hardness results for min-diameter approximation in the sparse cyclic versus acyclic cases.
This result, along with all other hardness results from SETH in this work, are via Orthogonal Vectors (OV) reductions. The OV problem is as follows: Given two sets A, B each containing n d-dimensional Boolean vectors, determine whether there are vectors a ∈ A and b ∈ B that are orthogonal, meaning a • b = 0.
). There is no constant ϵ > 0 such that for any constant c and d = c log n, the OV problem can be solved by a randomized algorithm in time O(n 2-ϵ ).
The OV Conjecture is implied by SETH [23]. OV-based sparse graph constructions have been commonly used to provide hardness results for diameter variants for the past decade, after having been first introduced by Roditty and Vassilevska W. in [20]. However, unlike previous OV-based constructions known to us, our construction is of a graph shaped as a cycle. If there are no orthogonal vectors then all vertices can reach one another via a single loop around the cycle, whereas if there are orthogonal vectors a path between them must loop nearly twice around the cycle, giving a min-diameter nearly twice as large.
As for upper bounds for general directed graphs, Dalirrooyfard et al. [15] gave for every integer k ≥ 2, an Õ(mn 1/k ) time (4k -5)-approximation algorithm for min-diameter. Most recently, Chechik and Zhang [11] achieved a 4-approximation in near-linear time. There is still a gap between the best approximation known in O(m 2-ε ) time (3 by [15]) and the best hardness result for such algorithms (2 by this work for unweighted, and by [2] for weighted).
A bichromatic version of diameter was considered by Dalirrooyfard et al. [14]. In a graph whose nodes are colored red and blue, the bichromatic diameter is the largest distance between two nodes of different colors. Dalirrooyfard et al. [14] gave algorithms and hardness for bichromatic diameter under the usual notion of distance.
Our work presents the first study of the notion of bichromatic min-diameter. As the min-diameter is the most natural diameter notion for DAGs, the bichromatic min-diameter is likewise a natural way to consider distances in DAGs whose vertices are two-colored.
We first give hardness for general directed graphs, suggesting that bichromatic mindiameter may be harder than regular min-diameter: ▶ Theorem 3. Under SETH, there can be no O(m 2-ε ) time ( 52 -δ)-approximation algorithm for bichromatic min-diameter in unweighted n-node, m = n 1+o(1) -edge graphs for ϵ, δ > 0.
Furthermore, under SETH, there can be no O(m 2-ε ) time (3-δ)-approximation algorithm for bichromatic min-diameter in graphs with O(log n) bit integer edge weights.
It would be interesting if the Õ(m √ n) 3-approximation algorithm for min-diameter of [15] can be extended to work for bichromatic min-diameter, as then one could get a tight result in the weighted case.
We next turn to bichromatic min-diameter in DAGs. We give an almost-2-approximation algorithm and show that it is essentially tight (up to the additive error) under SETH:
▶ Theorem 5. There is an Õ(m 4/foot_2 n 1/3 )-time algorithm, which, given a DAG and maximum red-blue edge weight M , outputs a (2, M )-approximation of the bichromatic min-diameter.
Finally, we present a linear-time algorithm which determines whether a directed graph has finite bichromatic min-diameter. The proof may be found in the full version of the paper [7].
▶ Theorem 6. There is an O(m) time algorithm which checks, for any weighted directed graph G, whether the bichromatic min-diameter is finite.
We assume the word-RAM model of computation with O(log n) bit words. All of our algorithms and reductions fall within this model.
Graphs in this work are directed and weakly connected. 3 Edge weights are polynomial in n.
The min-eccentricity of a vertex, ϵ(v), is given by max u∈V d min (u, v).
Given a DAG G with topological ordering π and vertex sets S, T ⊆ V = V (G), we write S < π T if all vertices in S appear to the left of all vertices in T . When S or T is equal to {x} for some vertex x, we may omit the brackets. For vertices s, t, we write s ≤ π t if s < π t or s = t. We define a closed subset (with respect to π) to be a subset S such that for all
Given a DAG G with topological ordering π, a vertex v ∈ V and a set S ⊆ V , let s v ∈ S be the left-most vertex in S such that d(v, s) ≤ D, if such an s v exists. Then we define N out D,S (v) to be the set of vertices w such that d(v, w) ≤ D and, if s v exists, w ≤ π s v . One can intuitively think of N out D,S (v) as the set N out D (v) of vertices at distance at most D from v, but cut off after the first (left-most) time we hit S. We define
A bichromatic DAG G is a DAG whose vertices are two-colored. An (A, B)-separated DAG, which we may also simply call a separated DAG is a DAG ordered according to some topological ordering π with color sets A, B such that A < π B.
We sometimes omit π when the choice of π is clear.
Let ω(1, r, 1) be the exponent of the runtime of multiplying n × n r by n r × n matrices. The square matrix multiplication exponent is ω = ω(1, 1, 1) > 2.37286 [4].
In this section, we review two useful techniques. The first of these is the greedy set cover lemma. This lemma, and a related randomized version, have been commonly used in prior work on diameter variants ( [3], [20], [8], [2], [13]). See [21] for a proof of the lemma.
The following technique, previously used in [13], constructs a set cover of all sufficiently large balls of radius d.
of out-neighbors of S t ∪ {v} that are at distance at most d from v. If W is nonempty, we let w be its left-most element, and we construct
Thus, in either case, we will eventually construct
The key step in this construction process, namely finding w, can be done by maintaining a list containing the left-most neighbor of each vertex in S t such that the neighbor is of distance at most d from v, and choosing the left-most vertex in the list at each step. At step t, this list has length at most |S t | < k, and the total number of steps is at most k, so the construction can be done in O(k 2 ) time.
We can construct
In Section 2.1 we present a conditional lower bound showing that the OV Conjecture implies that no (2 -δ)-approximation algorithm for min-diameter in unweighted graphs can run in truly subquadratic time. Subsequently, in Section 2.2, we give an almost-3 2 -approximation algorithm for min-diameter in unweighted DAGs which runs in truly subquadratic time.
We first present a conditional lower bound for approximating min-diameter in general graphs.
▶ Theorem 9. If there are ϵ, δ > 0 such that there is an O(m 2-ϵ )-time (2 -δ)-approximation algorithm for min-diameter, then the OV Conjecture is false.
Let A be an instance of single-set OV 4 , that is, a set of n ≥ 2 t vectors in {0, 1} c0 log n for a constant c 0 > 0. We will construct a graph G t with O(tn) vertices, Õ(tn) edges such that the min-diameter is 2t + 1 if A contains a pair of orthogonal vectors, and t + 1 otherwise. For each i ∈ [t], we construct a set A i of n vertices corresponding bijectively to the vectors in A. For each vector a ∈ A, let a i be the vertex in set A i corresponding to a. We also construct a set I of "index" vertices x 1 , . . . , x c log n . In total we have O(tn) vertices. We add an edge a 1 → x j and an edge x j → a t whenever a[j] = 1. We also add edges a i → a i-1 for each i ∈ {2, . . . , t}. Finally, we add all possible edges A 2 → I. In total we have Õ(tn) edges. This graph G t may be constructed in Õ(tn) = Õ(n) time.
We now check that if the OV instance is a YES instance, G t has at least min-diameter 2t + 1, and in the NO case, G t has min-diameter t + 1.
Let a, b ∈ A be orthogonal. Without loss of generality, d min (a 1 , b 1 ) = d(a 1 , b 1 ). There is no j such that a[j] = b[j] = 1, so there is no length-2 path from a 1 to b t via I. Since all edges between A i and A i-1 are of the form a i → a i-1 , the first t vertices on any a 1 → b 1 path must be of the form
We note that any path from c 2 to b 1 must traverse all sets of the cycle with the possible exception of A 1 , so must be of length at least t.
So G t has min-diameter at least 2t + 1.
Suppose that A contains no pair of orthogonal vectors. For any a 1 , b i , there is some j such that a
Lastly, for any a i ∈ A i with i ≥ 2, and for any x j ∈ I, there is a path a i → . . . a 2 → x j of length at most t. Hence, all pairs of vertices are at min-distance at most t + 1. ◀
Unlike in general directed graphs, where (2 -δ)-approximating min-diameter seems to be hard, in DAGs one can achieve an efficient ( 3 2 , 1 2 )-approximation and a (slightly less) efficient
3 2 -approximation. The ( 3 2 , 1 2
) and the exact 3 2 approximations have very similar proofs; we present the proof of the ( 3 2 , 1 2 )-approximation result here because the algorithm is faster and marginally simpler than in the exact 3 2 case, whose proof can be found in the full version of the paper [7].
Our algorithm uses fast sparse matrix multiplication to compute set intersections. Its runtime involves the constants α = max{0 ≤ r ≤ 1 | ω(1, r, 1) = 2} and β = ω-2 1-α .
▶ Theorem 10. There is an Õ(m 4β+2-2αβ 5β+3-2αβ n)-time algorithm achieving a ( 3 2 , 1 2 )-approximation for min-diameter in unweighted DAGs.
Since α > 0.31389 [17] and ω < 2.37286 [4], we can use β ≃ 0.5435, giving the runtime O(m 0.713 n).
The algorithm starts by topologically sorting the DAG and fixing a neighborhoodsize parameter k (whose value will be determined later). It then performs two layers of recursion. The outer layer is a binary search over min-diameter estimates D: for each estimate D, it will either determine that D is low or high, i.e. that min-diameter(G) > D or min-diameter(G) ≤ ⌈ 3 2 D⌉. The inner layer, in which the estimate D is fixed, involves recursively splitting the graph in half according to the topological ordering. Then, in the core body of the algorithm, one of the following will occur:
We find a pair of vertices with min-distance larger than D, in which case we end the recursion and report that min-diameter(G) > D.
We verify that every min-distance between a vertex in the left half and a vertex in the right half is at most ⌈3D/2⌉, and we recurse on the left and right halves of the graph.
The core body of the algorithm -which will be repeated recursively as the graph is repeatedly cut in half -is as follows:
First, using Lemma 8, we compute a (k, (D/2, ⌈D/2⌉))-neighborhood cover S of size O( n k log n) along with neighborhoods N out D/2,S (v), N in ⌈D/2⌉,S (v) all of which have size at most k. Using BFS, we check that d min (s, v) ≤ D for all s ∈ S, v ∈ V . This step ensures that, for every vertex with a "sufficiently large" (meaning, size-k) distance-D/2 out-neighborhood or distance-⌈D/2⌉ in-neighborhood, some vertex in S lies in that out-or in-neighborhood. In this sense, S covers all of the large neighborhoods, which will be useful later.
We partition
be the left and right halves of V . We start in the middle and work outwards verifying that min-distances between vertices in L and R are at most ⌈3D/2⌉.
At each inductive step, we consider two subsets of vertices A = V i and B = V j to the left and right of the "middle interval," which consists of the intervening subsets
Intuitively, one might picture the middle interval as a growing amoeba, which at each step engulfs one of A or B. We will only add vertices to the middle interval once they have been "checked," so vertices from A that are added to the middle interval have distance at most 3D/2 to everything in B, and vice-versa. Eventually, either the algorithm will detect a min-distance greater than D and report that min-diameter(G) > D, or the amoeba will have engulfed enough of the graph that it contains the entirety of one of the halves L or R, meaning that all distances from vertices in L to vertices in R are at most ⌈ 3 2 D⌉. In order to expand the middle interval we have to confirm that one of our two candidate subsets A and B has small distances to the opposite half of the graph. Performing a BFS from each vertex in A or B to confirm this directly would be too slow, so instead we present two subroutines to achieve this goal faster. Algorithm 2 checks that all min-distances between vertices a ∈ A and b ∈ B are at most ⌈3D/2⌉. Algorithm 3 checks that either all vertices in A have min-distance at most 3 2 D to all vertices to the right of B, or that a symmetric property holds for all vertices in B. These algorithms will either detect that the min-diameter is more than D or allow us to add one of A or B to the middle interval.
We first give a pseudocode description of the main algorithm, Algorithm 1, which will give context for the two subroutines, Algorithms 2 and 3, whose descriptions follow afterwards.
We will present the correctness and runtime analyses for the two subroutines, and then present the correctness proof and runtime analysis for the overall algorithm.
The first subroutine, Algorithm 2, checks distances between pairs of vertices in subsets A, B by using the cover S to hit large neighborhoods and using fast sparse rectangular matrix multiplication to efficiently check set intersections between small neighborhoods.
▶ Theorem 11 ([19]). If M, M ′ are p × l matrices having at most l nonzero entries, where
).
Proof. We first show correctness. Assume the algorithm fails; then it fails inside the foreach loop at some pair a, b. Suppose for the sake of contradiction that d min (a, b) ≤ D. Let x be a midpoint of the shortest path from a to b, so d(a, x)
,S (a) despite being distance ≤ D/2 from a, then x must lie after the outneighborhood of a reaches the (k, (D/2, ⌈D/2⌉))-neighborhood cover S and is cut off. That is, there is some s ∈ N out D/2 (a) ∩ S to the left of x, and hence to the left of b. Thus the condition in line 9 holds, and we continue rather than FAIL, which is a contradiction. Similarly, if x / ∈ N in ⌈D/2⌉,S (b) then the condition in line 7 holds, which is a contradiction. We conclude that x ∈ N out D/2,S (a) ∩ N in ⌈D/2⌉,S (b), in which case M ab ≥ 1, completing the contradiction. Thus, d min (a, b) > D, and so min-diameter(G) > D. Next we give the directional min-distance tester. A call to this subroutine will prove a min-distance bound of 3D/2 from A to everything past B, prove a bound of ⌈3D/2⌉ from B to everything before A, or find a pair of vertices with min-distance greater than D. The idea is to iterate over vertices a in A; those with large D/2-neighborhoods get hit by S, and if some a has a small D/2-neighborhood it can be used as a jumping-off set to show B is close to everything past A. Proof. This algorithm fails only when some s ∈ S has ϵ(s) > D, when Algorithm 2 fails, or Algorithm 3 fails, all of which imply min-diameter(G) > D. We now show that in the event of a pass, min-diameter(G) ≤ ⌈3D/2⌉. It suffices to prove that if the algorithm reaches line 13 then all min-distances between vertices in L and R are at most ⌈3D/2⌉. Assume we are at the beginning of iteration t of the while loop. Let I t = i<ℓ<j V ℓ be the interval strictly between V i and V j . We will show inductively that for all x ∈ L and y ∈ R, where at least one of x or y is in the interval I t , d min (x, y) ≤ ⌈3D/2⌉. When the loop terminates, I t must entirely contain either L or R, which will prove that all min-distance between vertices in L and R are at most ⌈3D/2⌉.
The base case is trivial, as I 1 is empty. Assume the claim holds for t. Without loss of generality, assume Algorithm 3 returns V i , so that I t+1 = I t ∪ V i . Let x ∈ L, y ∈ R with at least one of x or y in I t+1 . If x or y is in I t , then d(x, y) ≤ ⌈3D/2⌉ by induction. Otherwise, one must lie in I t+1 \ I t = V i , and since V i ⊂ L, this vertex must be x. Then we have y ∈ V j or y > π V j . If y ∈ V j , then since Algorithm 2 did not fail, we have d(x, y) ≤ 3D/2. If y > π V j , then because Algorithm 3 returned V i we have d(x, y) ≤ ⌈3D/2⌉. This completes the induction and the proof of correctness.
G can be topologically sorted in time Õ(n). Lemma 8 constructs the set S in time O(nk 2 ). Running BFS to and from each vertex in S takes time Õ(mn/k). We run Algorithm 2 and Algorithm 3 each up to 2θ = n/2k 2 times. Since Algorithm 2 takes time O(k 4+ 2β-2αβ β+1 ) and Algorithm 3 takes time O(mk), the total runtime of a recursive step is therefore: This runtime is at most O(m 1.426 n 0.288 ). We note that there is also a combinatorial version of this algorithm which runs in time Õ(m 5/4 n 1/2 ), and a version which runs in Õ(m 7β+3-3αβ 5β+3-2αβ n 2β+2-αβ 5β+3-2αβ ) time, which is O(m 1.171 n 0.543 ), when m ≤ n 1.283 . A proof of the theorem may be found in the full version of the paper [7].
We first present OV-based conditional lower bounds for bichromatic min-diameter approximations, both for general graphs and for DAGs. Then in Section 3.2, we give an almost-2-approximation algorithm for bichromatic min-diameter in DAGs.
We present, in order of increasing strength of the bound, three conditional lower bounds for approximating bichromatic min-diameter: one for DAGs, one for unweighted directed graphs, and one of weighted directed graphs. The constructions proceed analogously to Theorem 9, and can be found in the full version of the paper [7].
We conclude by turning to upper bounds for bichromatic min-diameter.
▶ Theorem 21. There is an Õ(min(m 4/3 n 1/3 , m 1/2 n 3/2 ))-time algorithm, which, given a DAG G with maximum red-blue edge weight M 0 , outputs an approximation D 0 such that D ≤ D 0 < 2D + M 0 ≤ 3D.
We give a brief overview of the algorithm. The full details and proof of correctness can be found in the full version of the paper [7].
We first consider the simpler case when the DAG is separated, i.e. when in some topological ordering every red vertex is to the left of every blue vertex. As is typical, we proceed by a binary search; at each stage we have some guess D for the bichromatic min-diameter and either verify the true bichromatic min-diameter is larger than D or smaller than 2D.
We begin by finding a hitting set for the red vertices with large red outneighborhoods (other red vertices at distance at most D). This is achieved via the standard sampling method (Lemma 8). By running a BFS from this hitting set, we can verify min-distances for all vertices hit in this way to the blue side are not large; it remains to control vertices with small red out-neighborhoods. This is handled separately for sparse and dense graphs.
The tilde hides polylogarithmic factors.
Combinatorial is here used to refer to an algorithm that does not rely on fast matrix multiplication.
If a graph is not weakly connected (which can be checked in O(m + n) time), then it has infinite min-diameter, as well as infinite bichromatic min-diameter if its vertices are 2-colored.
The OV Conjecture can be equivalently stated in terms of single-set OV (OV where A = B). Informally, the reduction is to construct A ′ from A by appending 10 to all vectors, and B ′ from B by appending 01 to all vectors. If v1, v2 ∈ A ′ ∪ B ′ are orthogonal, then we must have v1 ∈ A ′ , v2 ∈ B ′ or vice versa.
To be precise, if we have α ≥ a, ω ≤ c, we can define b = c-2 1-a , and then the theorem holds for any such pair a, b, used in place of α, β.