Real-weighted diameter and eccentricities of minor-free and bounded VC-dimension graphs in truly subquadratic time

We present the first truly subquadratic time algorithm to compute diameter and eccentricities in real-weighted directed graphs with constant distance VC-dimension and strongly sublinear-sized balanced separators. For real-weighted K_h-minor-free digraphs, this runs in O(n^{2-1/(2h-2)} polylog(n)) time. 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.