Lune

SODA2020Top-tier venue

Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension

Guillaume Ducoffe, Michel Habib, Laurent Viennot

Abstract

Under the Strong Exponential-Time Hypothesis, the diameter of general unweighted graphs cannot be computed in truly subquadratic time. 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 VC-dimension as a broad generalization of many such classes -where the distance VC-dimension of a graph G is defined as the VC-dimension of its ball hypergraph: whose hyperedges are the balls of all possible radii and centers in G. In particular for any fixed H, the class of H-minor free graphs has distance VC-dimension at most |V (H)| -1.

• Our first main result is a Monte Carlo algorithm that on graphs of distance VC-dimension at most d, for any fixed k, either computes the diameter or concludes that it is larger than k in time Õ(k • mn 1-ε d ), where ε d ∈ (0; 1) only depends on d. 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 the first 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.

• Finally, we show how to remove the dependency on k for any graph class that excludes a fixed graph H 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 subquadratictime randomized algorithm for computing their diameter.

We note that all our results also hold for radius computation. 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 ε-nets, region decomposition and other partition techniques.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

4 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers4

  1. Settling SETH vs. approximate sparse directed unweighted diameter (up to (NU)NSETH)Ray LiSTOC 2021 · 5 citations
  2. The Parameterized Complexity of Computing the VC-DimensionFlorent Foucaud, Harmender Gahlawat, Fionn Mc Inerney, Prafullkumar TaleNeurIPS 2025 · 2 citations
  3. VC Set Systems in Minor-free (Di)Graphs and ApplicationsHung Le, Christian Wulff-NilsenSODA 2024
  4. Non-Clashing Teaching in Graphs: Algorithms, Complexity, and BoundsSujoy Bhore, Liana Khazaliya, Fionn Mc InerneyICLR 2026

Related papers

  1. Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimensionTimothy M. Chan, Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak et al.FOCS 2025 · 1 citation
  2. Tight conditional lower bounds for approximating diameter in directed graphsMina Dalirrooyfard, Nicole WeinSTOC 2021 · 3 citations
  3. Constant Approximation of Min-Distances in Near-Linear TimeShiri Chechik, Tianyi ZhangFOCS 2022 · 1 citation
  4. Subquadratic algorithms in minor-free digraphs: (weighted) distance oracles, decrementai reachability, and moreAdam Karczmarz, Da Wei ZhengSODA 2025
  5. Certificates in P and Subquadratic-Time Computation of Radius, Diameter, and all Eccentricities in GraphsFeodor F. Dragan, Guillaume Ducoffe, Michel Habib, Laurent ViennotSODA 2025
Dusk over the sea between two cliffs drawn in fine vertical lines