Improved Approximation of Min-Distances in Near-Linear Time
2026-07-10 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study how to estimate the diameter of directed graphs when using the min-distance measure, which is different from normal distances because it takes the smaller of the two possible directions between nodes. Previous methods gave rough approximations or took longer to run. The authors present a new randomized algorithm that finds a 3-approximation of this diameter quickly, improving on all earlier results. They also extend their method to a more complex model called multimode graphs, achieving much better approximations than before. Their work helps better understand graph distances that don’t behave like usual metrics.
directed graphsgraph diametermin-distanceapproximation algorithmsrandomized algorithmsmultimode graphsnon-metric distanceruntime complexitytype-classification frameworkshortest path
Authors
Yael Kirkpatrick
Abstract
We study the problem of approximating the diameter of directed graphs under the min-distance measure, defined as $d_{\min}(u,v) = \min(d(u,v), d(v,u))$. Unlike standard shortest-path distance, min-distance is not a metric, which renders many classical techniques inapplicable. Prior work has therefore focused on approximating this parameter, culminating in an approximation-runtime tradeoff by Dalirrooyfard et al. [ICALP'19] giving a $4k-1$ approximation in $\tilde{O}(mn^{1/(k+1)})$ time for any positive integer $k$ and, more recently, the first near-linear time constant approximation by Chechik and Zhang [FOCS'22], where they obtained a 4-approximation to the min-diameter. In this work we present a randomized near-linear time algorithm that achieves a $3$-approximation to the min-diameter, outperforming all known approximation-runtime tradeoffs. Our approach introduces a novel type-classification framework that may be of independent interest. We further extend our techniques to the more general setting of multimode graphs, recently introduced as a generalization of min-distance by Kirkpatrick and Vassilevska W. [MFCS'25]. For directed $2$-mode graphs, we obtain a $3$-approximation to the diameter in near-linear time, dramatically improving over the previously best known $n$-approximation. Our results significantly narrow the gap between min-distance and multimode distance approximations, and open new directions for understanding graph parameters under non-metric distance measures.