我们提出了第一个真正亚二次时间算法，用于计算具有常数距离 VC-维数和强亚线性大小平衡分离子的真实加权有向图的直径和离心率。该算法在真实加权的 $K_h$-小图中运行时间为 $O(n^{2-1/(2h-2)}\mathrm{polylog}(n))$。在此之前，真正亚二次时间的直径计算仅在真实加权平面图中得到应用，而对更广泛类别如小图的扩展则仅限于无权设置。
特别是，现有利用 VC-维数的算法 [Ducoffe, Habib, Viennot; SICOMP 2022][Le, Wulff-Nilsen; SODA 2024][Chan, Chang, Gao, Le, Kisfaludi-Bak, Zheng; FOCS 2025] 处理小整数权重，但并未自然推广到真实权重。我们通过引入随机搜索到决策的归约，克服了这一障碍，证明了在真实加权情况下，VC-维数是一个足够强大的工具。
博主点评： 该研究为图论领域带来了显著的进展，尤其是在处理真实加权图时的效率提升。通过引入随机化方法，研究者成功地将 VC-维数的应用推广至更复杂的图形类型，显示出其在实际应用中的潜力。这一算法的实现将为未来的图算法研究指明方向。