{"ID":5675256,"CreatedAt":"2026-07-03T01:40:09.565152011Z","UpdatedAt":"2026-07-07T01:06:03.009715918Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.01926","arxiv_id":"2607.01926","title":"Real-weighted Diameter and Eccentricity of Minor-free and Bounded VC-dimension Graphs in Truly Subquadratic Time","abstract":"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)}\\textrm{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.","short_abstract":"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)}\\textrm{polylog}(n))$ time for real-weighted $K_h$-minor-free digraphs. Prior t...","url_abs":"https://arxiv.org/abs/2607.01926","url_pdf":"https://arxiv.org/pdf/2607.01926v1","authors":"[\"Da Wei Zheng\"]","published":"2026-07-02T09:22:33Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}