2023/08/16 by Berger, Aaron, Kaufmann, Jenny, Williams, Virginia Vassilevska · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2308.08674
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 dmin(u,v) across all pairs u,v ∈ V(G), where dmin(u,v) = min(d(u,v), d(v,u)). Our work provides a O(m1.426n0.288)-time 3/2-approximation algorithm for min-diameter in DAGs, and a faster O(m0.713n)-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.