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

Jul 16, 2026

First truly subquadratic-time algorithm computes diameter and eccentricity in real-weighted directed graphs under constant-distance VC-dimension together with strongly sublinear-sized balanced separators. The runtime achieves O(n2−1/(2h−2) polylog(n)) for real-weighted Kh-minor-free digraphs. Prior work achieved subquadratic diameter mainly for real-weighted planar graphs or for minor-free graphs only in unweighted/integer-weight regimes. This paper introduces a randomized search-to-decision reduction to enable real-weight handling and shows VC-dimension remains algorithmically powerful in that setting.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages12

Reading Time30 min

Abstract

Introduction

Our Contribution

arXiv :2607 .0 1926v 1 [ cs .DS] 2 Jul 2026 Real-weighted Diameter and Eccentricity of Minor-free and Bounded VC-dimension Graphs in Truly Subquadratic Time Da Wei Zheng* July 3, 2026 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(n2−1/(2h−2)polylog(n)) time for real-weighted Kh-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, KisfaludiBak, 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. 1 Introduction For a sparse graph G with n vertices and O (n) non-negative real-weighted edges, it is possible to comthepgutrapehtheHoiametever, erevoe Gin e(n2igh)tteimd ue1nby runndirectedingrg Daph,kstracom’s aputligongrthhemerom everact diameytevrrtnetxruofly subquadratic time is impossible assuming the Strong Exponential Time Hypothesis (SETH) [RV13 ] . This negative result has motivated the study of diameter in structured graph classes where truly subquadratic-time diameter is achievable, such as bounded-treewidth graphs [CK09, BHM20 ], planar graphs [Cab19, GKM+21], bounded genus graphs [KPPS25 ], Kh-minor-free graphs [DHV22, LW24, KZ25 ], and geometric intersection graphs [DKP24, CCG+25] . Two major paradigms have emerged for breaking this quadratic barrier for structured graph classes. The first is abstract Voronoi diagrams for planar graphs that were pioneered by Cabello [Cab19] atWiiemloeenKirilye wWiluaaatmacicptr-mveorae5/rr3aam) loyelmrypoenlgrKreaaappl-sneti,haMghtotensa,inShndri(,11/6anctedd) settings, the approach strongly relies on planarity and is likely only generalizable to bounded-genus graphs. The second paradigm revolves around VC-dimension. Ducoffe, Habib, and Viennot [DHV22 ] demonstrated that it is possible to get a truly subquadratic-time algorithm in undirected unweighted Kh-minor-free graph with distance VC-dimension, the VC-dimension of neighborhood balls centered *This project has received funding from the Austrian Science Fund (FWF) grant DOI 10.55776/I5982 . For open access purposes, the author has applied a CC BY public copyright license to any author-accepted manuscript version arising from this submission. 1Throughout this paper, we will use (·) to suppress polylogarithmic factors of n. Graph class Runtime Real-weighted? Planar O (n11/6) (n5/3) Y Y [Cab19][GKM+21] Kh-minor-free (((11////((2O32((h222))))) N N N N [DHV22 ][LW24 ] [KZ25 ][CCG+25] (n2−1/(2h−2)) Y Corollary 2 O (nβ)-separator g.d. VC-dim d 2(−n2(β/()/22dO) )(d)) N N [DHV22 ][CCG+25] (n2−(1−β )/d ) Y Theorem 1 g.d. VC-dim d O (mn1−1/(2d)) N [CCG+25] e Table 1: Summary of runtime guarantees for diameter and eccentricity algorithms in directed graphs with n vertices and m edges. Generalized distance VC-dimension is abbreviated as “g.d. VC-dim”. All bounds are for directed graphs. Note that all graphs besides g.d. VC-dim d graphs are sparse and have m = O (n) . at every vertex of the graph. Le and Wulff-Nilsen [LW24 ] generalized a different bounded VCdimension set system –distance profiles – studied by Li and Parter [LP19 ] in planar graphs to obtain results for directed Kh-minor-free graphs. Bounds on both distance VC-dimension and distance profiles were unified by Karczmarz and Zheng [KZ25 ] with generalized distance VC-

FAQs

What problem does the paper address?

The paper addresses computing graph diameter and vertex eccentricities in real-weighted directed graphs efficiently, specifically in truly subquadratic time under structural constraints.

What are the key assumptions enabling the algorithm?

The approach relies on constant distance VC-dimension and strongly sublinear-sized balanced separators, and targets monotone graph families such as real-weighted Kh-minor-free digraphs.

How does the paper overcome the difficulty of real edge weights?

It introduces a randomized search-to-decision reduction, showing that VC-dimension tools can be adapted to the real-weighted regime where earlier algorithmic machinery did not generalize well.

Jul 16, 2026

Upload by Emma Wilson