Diameter, Eccentricities and Distance Oracle Computations on H -Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension
Guillaume Ducoffe, Michel Habib, Laurent Viennot · SIAM Journal on Computing · 2022
Abstract. Under the strong exponential-time hypothesis, the diameter of general unweighted graphs cannot be computed in truly subquadratic time (in the size [Formula: see text] of the input), as shown by Roditty and Williams. Nevertheless there are several graph classes for which this can be done such as bounded-treewidth graphs, interval graphs, and planar graphs, to name a few. We propose to study unweighted graphs of constant distance Vapnik–Chervonenkis (VC)-dimension as a broad generalization of many such classes—where the distance VC-dimension of a graph [Formula: see text] is defined as the VC-dimension of its ball hypergraph whose hyperedges are the balls of all possible radii and centers in [Formula: see text]. In particular for any fixed [Formula: see text], the class of [Formula: see text]-minor free graphs has distance VC-dimension at most [Formula: see text]. Our first main result is a Monte Carlo algorithm that on graphs of distance VC-dimension at most [Formula: see text], for any fixed [Formula: see text], either computes the diameter or concludes that it is larger than [Formula: see text] in time [Formula: see text], where [Formula: see text] only depends on [Formula: see text] and the [Formula: see text] notation suppresses polylogarithmic factors. We thus obtain a truly subquadratic-time parameterized algorithm for computing the diameter on such graphs. Then as a byproduct of our approach, we get a truly subquadratic-time randomized algorithm for constant diameter computation on all the nowhere dense graph classes. The latter classes include all proper minor-closed graph classes, bounded-degree graphs, and graphs of bounded expansion. Before our work, the only known such algorithm was resulting from an application of Courcelle’s theorem; see Grohe, Kreutzer, and Siebertz [ J. ACM, 64 (2017), pp. 1–32]. For any graph of constant distance VC-dimension, we further prove the existence of an exact distance oracle in truly subquadratic space, that answers distance queries in truly sublinear time (in the number [Formula: see text] of vertices). The latter generalizes prior results on proper minor-closed graph classes to a much larger graph class. Finally, we show how to remove the dependency on [Formula: see text] for any graph class that excludes a fixed graph [Formula: see text] as a minor. More generally, our techniques apply to any graph with constant distance VC-dimension and polynomial expansion (or equivalently having strongly sublinear balanced separators). As a result for all such graphs one obtains a truly subquadratic-time deterministic algorithm for computing all the eccentricities, and thus both the diameter and the radius. Our approach can be generalized to the [Formula: see text]-minor free graphs with bounded positive integer weights. We note that all our algorithms for the diameter problem can be adapted for computing the radius, and more generally all the eccentricities. Our approach is based on the work of Chazelle and Welzl who proved the existence of spanning paths with strongly sublinear stabbing number for every hypergraph of constant VC-dimension. We show how to compute such paths efficiently by combining known algorithms for the stabbing number problem with a clever use of [Formula: see text]-nets, region decomposition, and other partition techniques.