We present the first truly subquadratic time algorithm to compute diameter and eccentricity in real-weighted directed graphs with constant distance VC-dimension and strongly sublinear-sized balanced separators. This runs in $O(n^{2-1/(2h-2)}\mathrm{polylog}(n))$ time for real-weighted $K_h$-minor-free digraphs. Prior to this work, truly subquadratic time computation of diameter was only known for real-weighted planar graphs, while extensions to broader classes like minor-free graphs were restricted to unweighted settings.
In particular, existing algorithms that use VC-dimension [Ducoffe, Habib, Viennot; SICOMP 2022][Le, Wulff-Nilsen; SODA 2024][Chan, Chang, Gao, Le, Kisfaludi-Bak, Zheng; FOCS 2025] work with small integer weights but do not naturally generalize to real weights. We overcome this barrier by introducing a randomized search-to-decision reduction, demonstrating that VC-dimension is a sufficiently powerful tool in the real-weighted regime.
Blogger's Review: This research marks a significant advancement in the field of graph theory, particularly in enhancing the efficiency of handling real-weighted graphs. By introducing a randomized approach, the authors successfully expanded the application of VC-dimension to more complex graph types, showcasing its potential in practical applications. The implementation of this algorithm will guide future research in graph algorithms.