pith. sign in

arxiv: 2607.01926 · v1 · pith:P65D2I3Gnew · submitted 2026-07-02 · 💻 cs.DS

Real-weighted Diameter and Eccentricity of Minor-free and Bounded VC-dimension Graphs in Truly Subquadratic Time

Da Wei Zheng This is my paper

Pith reviewed 2026-07-03 04:16 UTC · model grok-4.3

classification 💻 cs.DS
keywords diameter computationeccentricityminor-free graphsVC-dimensionsubquadratic algorithmsreal-weighted graphsdirected graphsbalanced separators
0
0 comments X

The pith

A randomized search-to-decision reduction yields the first truly subquadratic algorithm for diameter and eccentricity in real-weighted K_h-minor-free digraphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes the first truly subquadratic time algorithm for computing diameter and eccentricity in real-weighted directed graphs that possess constant distance VC-dimension and strongly sublinear-sized balanced separators. Prior results achieved this only for real-weighted planar graphs or for unweighted minor-free graphs. The work overcomes the limitation of existing VC-dimension algorithms, which handled only small integer weights, by introducing a randomized search-to-decision reduction that preserves the subquadratic bound. This matters for fundamental graph problems because many real-world networks carry real-valued distances yet belong to minor-free classes with good separators.

Core claim

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)} polylog(n)) time for real-weighted K_h-minor-free digraphs by means of a randomized search-to-decision reduction that extends VC-dimension techniques from the integer-weighted regime.

What carries the argument

The randomized search-to-decision reduction that converts real-weighted diameter queries into integer-weighted instances while retaining subquadratic runtime and correctness under constant distance VC-dimension.

If this is right

  • Diameter and eccentricity become computable in O(n^{2-1/(2h-2)} polylog n) time for every fixed h in real-weighted K_h-minor-free digraphs.
  • VC-dimension methods apply directly to real-weighted graphs whenever the input admits strongly sublinear balanced separators.
  • The barrier that prevented integer-weight VC-dimension algorithms from generalizing to real weights is removed.
  • Truly subquadratic diameter computation extends beyond planar graphs to the full minor-free hierarchy in the weighted setting.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same reduction may shorten other distance problems, such as all-pairs shortest paths, in real-weighted graphs with bounded VC-dimension.
  • Practical implementations could accelerate distance queries in transportation networks whose underlying graphs are minor-free.
  • The technique invites generalization to undirected graphs or to graphs whose separators are only mildly sublinear.

Load-bearing premise

The randomized search-to-decision reduction correctly extends VC-dimension techniques from integer to real weights while preserving the subquadratic bound.

What would settle it

A concrete real-weighted K_h-minor-free digraph with constant distance VC-dimension on which the reduction either returns an incorrect diameter value or requires quadratic time.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper claims the first truly subquadratic algorithm for diameter and eccentricity in real-weighted directed graphs that have constant distance VC-dimension and strongly sublinear balanced separators. For real-weighted K_h-minor-free digraphs the running time is O(n^{2-1/(2h-2)} polylog n). The key technical step is a new randomized search-to-decision reduction that extends prior VC-dimension techniques (previously limited to small integer weights) to real weights while preserving the subquadratic exponent.

Significance. If the reduction is correct, the result meaningfully enlarges the class of graphs for which truly subquadratic diameter computation is known, moving from unweighted or integer-weighted minor-free graphs and real-weighted planar graphs to real-weighted minor-free graphs. The reduction itself, if it works with only polylog oracle calls and without inflating the separator size, would be a reusable tool for other real-weighted problems that rely on VC-dimension or separator structure.

major comments (1)
  1. [Abstract and reduction section] The randomized search-to-decision reduction is the sole bridge from the integer-weight results cited in the abstract to the real-weight claim. No derivation, proof sketch, or bound on the number of oracle calls appears in the abstract, and the full manuscript must explicitly show that the reduction uses only polylog(n) calls, introduces no super-polylog discretization cost, and preserves both the constant VC-dimension and the strongly sublinear balanced-separator property under real distances; otherwise the stated O(n^{2-1/(2h-2)}) exponent does not follow.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful review and for highlighting the centrality of the randomized search-to-decision reduction. We address the single major comment below.

read point-by-point responses

  1. Referee: [Abstract and reduction section] The randomized search-to-decision reduction is the sole bridge from the integer-weight results cited in the abstract to the real-weight claim. No derivation, proof sketch, or bound on the number of oracle calls appears in the abstract, and the full manuscript must explicitly show that the reduction uses only polylog(n) calls, introduces no super-polylog discretization cost, and preserves both the constant VC-dimension and the strongly sublinear balanced-separator property under real distances; otherwise the stated O(n^{2-1/(2h-2)}) exponent does not follow.

    Authors: The full manuscript contains a self-contained derivation of the reduction (Section 3). It establishes that the procedure makes O(polylog n) calls to the integer-weight decision oracle with high probability, incurs only polylogarithmic discretization overhead, and preserves both constant distance VC-dimension and the strongly sublinear balanced-separator property when distances are real-valued. Consequently the O(n^{2-1/(2h-2)}) exponent carries over unchanged. We agree that a concise proof sketch of these three properties would improve the abstract and are happy to insert one. revision: partial

Circularity Check

0 steps flagged

Minor self-citation in prior VC-dimension citations; new reduction introduced independently

full rationale

The paper's central claim rests on a newly introduced randomized search-to-decision reduction that extends prior VC-dimension techniques (cited from Ducoffe et al. SICOMP 2022, Le-Wulff-Nilsen SODA 2024, and Chan et al. FOCS 2025) to real weights. The FOCS 2025 citation overlaps with the present author but is invoked only for the integer-weight case that the abstract explicitly states does not generalize; the reduction itself is presented as original and is not derived from or equivalent to any cited result by construction. No equations, definitions, or fitted parameters in the abstract reduce the O(n^{2-1/(2h-2)} polylog n) bound to inputs. The derivation chain is therefore self-contained against external benchmarks with only a non-load-bearing self-citation.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The result rests on the graph classes satisfying constant distance VC-dimension and strongly sublinear balanced separators, plus the correctness of the newly introduced randomized reduction; these are domain assumptions rather than derived quantities.

axioms (2)
  • domain assumption Input graphs have constant distance VC-dimension
    Required for the VC-dimension machinery to yield subquadratic time; stated as a precondition in the abstract.
  • domain assumption Input graphs possess strongly sublinear-sized balanced separators
    Needed to obtain the specific exponent 2-1/(2h-2); listed alongside VC-dimension in the abstract.
invented entities (1)
  • randomized search-to-decision reduction no independent evidence
    purpose: Converts the search version of diameter into a decision version so that existing VC-dimension algorithms apply to real weights
    Introduced in the abstract as the device that overcomes the barrier preventing prior VC-dimension methods from handling real weights.

pith-pipeline@v0.9.1-grok · 5720 in / 1580 out tokens · 39794 ms · 2026-07-03T04:16:29.754196+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

33 extracted references · 31 canonical work pages

  1. [1]

    Better Diameter Algorithms for Bounded VC-Dimension Graphs and Geometric Intersection Graphs , booktitle =

    Lech Duraj and Filip Konieczny and Krzysztof Potepa , editor =. Better Diameter Algorithms for Bounded VC-Dimension Graphs and Geometric Intersection Graphs , booktitle =. 2024 , _url =. doi:10.4230/LIPICS.ESA.2024.51 , timestamp =

    work page doi:10.4230/lipics.esa.2024.51 2024

  2. [2]

    2022 , _url =

    Guillaume Ducoffe and Michel Habib and Laurent Viennot , title =. 2022 , _url =. doi:10.1137/20M136551X , timestamp =

    work page doi:10.1137/20m136551x 2022

  3. [3]

    Computing Diameter+2 in Truly-Subquadratic Time for Unit-Disk Graphs , booktitle =

    Hsien. Computing Diameter+2 in Truly-Subquadratic Time for Unit-Disk Graphs , booktitle =. 2024 , _url =. doi:10.4230/LIPICS.SOCG.2024.38 , timestamp =

    work page doi:10.4230/lipics.socg.2024.38 2024

  4. [4]

    Proceedings of the 2024

    Hung Le and Christian Wulff. Proceedings of the 2024. 2024 , _url =. doi:10.1137/1.9781611977912.192 , timestamp =

    work page doi:10.1137/1.9781611977912.192 2024

  5. [5]

    Subquadratic algorithms in minor-free digraphs: (weighted) distance oracles, decremental reachability, and more , booktitle =

    Adam Karczmarz and Da Wei Zheng , editor =. Subquadratic algorithms in minor-free digraphs: (weighted) distance oracles, decremental reachability, and more , booktitle =. 2025 , _url =. doi:10.1137/1.9781611978322.147 , timestamp =

    work page doi:10.1137/1.9781611978322.147 2025

  6. [6]

    Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications , booktitle =

    Christian Wulff. Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications , booktitle =. 2011 , _url =. doi:10.1109/FOCS.2011.15 , timestamp =

    work page doi:10.1109/focs.2011.15 2011

  7. [7]

    Valiant and Vijay V

    Leslie G. Valiant and Vijay V. Vazirani , title =. Theor. Comput. Sci. , volume =. 1986 , _url =. doi:10.1016/0304-3975(86)90135-0 , timestamp =

    work page doi:10.1016/0304-3975(86)90135-0 1986

  8. [8]

    Separator Theorem for Minor-Free Graphs in Linear Time , journal =

    \'. Separator Theorem for Minor-Free Graphs in Linear Time , journal =. 2025 , _url =. doi:10.48550/ARXIV.2512.01587 , eprinttype =

    work page doi:10.48550/arxiv.2512.01587 2025

  9. [9]

    2021 , _url =

    Pawel Gawrychowski and Haim Kaplan and Shay Mozes and Micha Sharir and Oren Weimann , title =. 2021 , _url =. doi:10.1137/18M1193402 , timestamp =

    work page doi:10.1137/18m1193402 2021

  10. [10]

    2019 , _url =

    Sergio Cabello , title =. 2019 , _url =. doi:10.1145/3218821 , timestamp =

    work page doi:10.1145/3218821 2019

  11. [11]

    2024 , month =

    Har-Peled, Sariel , title =. 2024 , month =

    2024

  12. [12]

    On Spanning Trees with Low Crossing Numbers , booktitle =

    Emo Welzl , editor =. On Spanning Trees with Low Crossing Numbers , booktitle =. 1992 , _url =. doi:10.1007/3-540-55488-2\_30 , timestamp =

    work page doi:10.1007/3-540-55488-2 1992

  13. [13]

    Bernard Chazelle and Emo Welzl , title =. Discret. Comput. Geom. , volume =. 1989 , _url =. doi:10.1007/BF02187743 , timestamp =

    work page doi:10.1007/bf02187743 1989

  14. [14]

    Vazirani , title =

    Rohit Khandekar and Satish Rao and Umesh V. Vazirani , title =. J. 2009 , _url =. doi:10.1145/1538902.1538903 , timestamp =

    work page doi:10.1145/1538902.1538903 2009

  15. [15]

    Expander Decomposition and Pruning: Faster, Stronger, and Simpler , booktitle =

    Thatchaphol Saranurak and Di Wang , editor =. Expander Decomposition and Pruning: Faster, Stronger, and Simpler , booktitle =. 2019 , _url =. doi:10.1137/1.9781611975482.162 , timestamp =

    work page doi:10.1137/1.9781611975482.162 2019

  16. [16]

    Computing Cut-Based Hierarchical Decompositions in Almost Linear Time , booktitle =

    Harald R. Computing Cut-Based Hierarchical Decompositions in Almost Linear Time , booktitle =. 2014 , _url =. doi:10.1137/1.9781611973402.17 , timestamp =

    work page doi:10.1137/1.9781611973402.17 2014

  17. [17]

    54th Annual

    Jonah Sherman , title =. 54th Annual. 2013 , _url =. doi:10.1109/FOCS.2013.36 , timestamp =

    work page doi:10.1109/focs.2013.36 2013

  18. [18]

    Approximate Undirected Maximum Flows in

    Richard Peng , editor =. Approximate Undirected Maximum Flows in. Proceedings of the Twenty-Seventh Annual. 2016 , _url =. doi:10.1137/1.9781611974331.CH130 , timestamp =

    work page doi:10.1137/1.9781611974331.ch130 2016

  19. [19]

    Frederickson , title =

    Greg N. Frederickson , title =. 1987 , _url =. doi:10.1137/0216064 , timestamp =

    work page doi:10.1137/0216064 1987

  20. [20]

    Strongly Sublinear Separators and Polynomial Expansion , journal =

    Zdenek Dvor. Strongly Sublinear Separators and Polynomial Expansion , journal =. 2016 , _url =. doi:10.1137/15M1017569 , timestamp =

    work page doi:10.1137/15m1017569 2016

  21. [21]

    Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs , journal =

    Sariel Har. Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs , journal =. 2017 , _url =. doi:10.1137/16M1079336 , timestamp =

    work page doi:10.1137/16m1079336 2017

  22. [22]

    Fast approximation algorithms for the diameter and radius of sparse graphs , booktitle =

    Liam Roditty and Virginia. Fast approximation algorithms for the diameter and radius of sparse graphs , booktitle =. 2013 , _url =. doi:10.1145/2488608.2488673 , timestamp =

    work page doi:10.1145/2488608.2488673 2013

  23. [23]

    Sergio Cabello and Christian Knauer , title =. Comput. Geom. , volume =. 2009 , _url =. doi:10.1016/J.COMGEO.2009.02.001 , timestamp =

    work page doi:10.1016/j.comgeo.2009.02.001 2009

  24. [24]

    Multivariate Analysis of Orthogonal Range Searching and Graph Distances , journal =

    Karl Bringmann and Thore Husfeldt and M. Multivariate Analysis of Orthogonal Range Searching and Graph Distances , journal =. 2020 , _url =. doi:10.1007/S00453-020-00680-Z , timestamp =

    work page doi:10.1007/s00453-020-00680-z 2020

  25. [25]

    Faster Diameter Computation in Graphs of Bounded Euler Genus , booktitle =

    Kacper Kluk and Marcin Pilipczuk and Michal Pilipczuk and Giannos Stamoulis , editor =. Faster Diameter Computation in Graphs of Bounded Euler Genus , booktitle =. 2025 , _url =. doi:10.4230/LIPICS.ICALP.2025.109 , timestamp =

    work page doi:10.4230/lipics.icalp.2025.109 2025

  26. [26]

    Planar diameter via metric compression , booktitle =

    Jason Li and Merav Parter , editor =. Planar diameter via metric compression , booktitle =. 2019 , _url =. doi:10.1145/3313276.3316358 , timestamp =

    work page doi:10.1145/3313276.3316358 2019

  27. [27]

    Covering Planar Graphs with a Fixed Number of Balls , journal =

    Victor Chepoi and Bertrand Estellon and Yann Vax. Covering Planar Graphs with a Fixed Number of Balls , journal =. 2007 , _url =. doi:10.1007/S00454-006-1260-0 , timestamp =

    work page doi:10.1007/s00454-006-1260-0 2007

  28. [28]

    VC-dimension and Erd

    Nicolas Bousquet and St. VC-dimension and Erd. Discret. Math. , volume =. 2015 , _url =

    2015

  29. [29]

    Almost Optimal Exact Distance Oracles for Planar Graphs , journal =

    Panagiotis Charalampopoulos and Pawel Gawrychowski and Yaowei Long and Shay Mozes and Seth Pettie and Oren Weimann and Christian Wulff. Almost Optimal Exact Distance Oracles for Planar Graphs , journal =. 2023 , _url =. doi:10.1145/3580474 , timestamp =

    work page doi:10.1145/3580474 2023

  30. [30]

    A Fast Approximation Algorithm for the Minimum Balanced Vertex Separator in a Graph , journal =

    Vladimir Kolmogorov and Jack Spalding. A Fast Approximation Algorithm for the Minimum Balanced Vertex Separator in a Graph , journal =. 2026 , _url =. doi:10.48550/ARXIV.2603.15782 , eprinttype =. 2603.15782 , timestamp =

    work page doi:10.48550/arxiv.2603.15782 2026

  31. [31]

    Liu and Richard Peng and Maximilian Probst Gutenberg and Sushant Sachdeva , title =

    Li Chen and Rasmus Kyng and Yang P. Liu and Richard Peng and Maximilian Probst Gutenberg and Sushant Sachdeva , title =. J. 2025 , _url =. doi:10.1145/3728631 , timestamp =

    work page doi:10.1145/3728631 2025

  32. [32]

    Probabilistic Tools for the Analysis of Randomized Optimization Heuristics , booktitle =

    Benjamin Doerr , editor =. Probabilistic Tools for the Analysis of Randomized Optimization Heuristics , booktitle =. 2020 , _url =. doi:10.1007/978-3-030-29414-4\_1 , timestamp =

    work page doi:10.1007/978-3-030-29414-4 2020

  33. [33]

    Chan and Hsien

    Timothy M. Chan and Hsien. Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension , booktitle =. 2025 , _url =. doi:10.1109/FOCS63196.2025.00140 , timestamp =

    work page doi:10.1109/focs63196.2025.00140 2025