The min-diameter of a directed graph $G$ is a measure of the largest distance between nodes. It is equal to the maximum min-distance $d_{min}(u,v)$ across all pairs $u,v \in V(G)$, where $d_{min}(u,v) = \min(d(u,v), d(v,u))$. Our work provides a $O(m^{1.426}n^{0.288})$-time $3/2$-approximation algorithm for min-diameter in DAGs, and a faster $O(m^{0.713}n)$-time almost-$3/2$-approximation variant. (An almost-$α$-approximation algorithm determines the min-diameter to within a multiplicative factor of $α$ plus constant additive error.) By a conditional lower bound result of [Abboud et al, SODA 2016], a better than $3/2$-approximation can't be achieved in truly subquadratic time under the Strong Exponential Time Hypothesis (SETH), so our result is conditionally tight. We additionally obtain a new conditional lower bound for min-diameter approximation in general directed graphs, showing that under SETH, one cannot achieve an approximation factor below 2 in truly subquadratic time. We also present the first study of approximating bichromatic min-diameter, which is the maximum min-distance between oppositely colored vertices in a 2-colored graph.

Graph parameters such as the diameter, radius, and vertex eccentricities are not defined in a useful way in Directed Acyclic Graphs (DAGs) using the standard measure of distance, since for any two nodes, there is no path between them in one of the two directions. So it is natural to consider the distance between two nodes as the length of the shortest path in the direction in which this path exists, motivating the definition of the min-distance. The min-distance between two nodes u and v is the minimum of the shortest path distances from u to v and from v to u. As with the standard distance problems, the Strong Exponential Time Hypothesis [Impagliazzo-Paturi-Zane 2001, Calabro-Impagliazzo-Paturi 2009] leaves little hope for computing min-distance problems faster than computing All Pairs Shortest Paths, which can be solved in Õ(mn) time. So it is natural to resort to approximation algorithms in Õ(mn^{1-ε}) time for some positive ε. Abboud, Vassilevska W., and Wang [SODA 2016] first studied min-distance problems achieving constant factor approximation algorithms on DAGs, and Dalirrooyfard et al [ICALP 2019] gave the first constant factor approximation algorithms on general graphs for min-diameter, min-radius and min-eccentricities. Abboud et al obtained a 3-approximation algorithm for min-radius on DAGs which works in Õ(m√n) time, and showed that any (2-δ)-approximation requires n^{2-o(1)} time for any δ > 0, under the Hitting Set Conjecture. We close the gap, obtaining a 2-approximation algorithm which runs in Õ(m√n) time. As the lower bound of Abboud et al only works for sparse DAGs, we further show that our algorithm is conditionally tight for dense DAGs using a reduction from Boolean matrix multiplication. Moreover, Abboud et al obtained a linear time 2-approximation algorithm for min-diameter along with a lower bound stating that any (3/2-δ)-approximation algorithm for sparse DAGs requires n^{2-o(1)} time under SETH. We close this gap for dense DAGs by obtaining a 3/2-approximation algorithm which works in O(n^{2.350}) time and showing that the approximation factor is unlikely to be improved within O(n^{ω - o(1)}) time under the high dimensional Orthogonal Vectors Conjecture, where ω is the matrix multiplication exponent.