Skip to Main content Skip to Navigation
Conference papers

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

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 sublin-ear balanced separators). As a result for all such graphs one obtains a truly subquadratic-time 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [63 references]  Display  Hide  Download

https://hal.inria.fr/hal-02340382
Contributor : Laurent Viennot <>
Submitted on : Wednesday, October 30, 2019 - 6:32:02 PM
Last modification on : Friday, June 12, 2020 - 5:38:05 PM

File

vc-diameter.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02340382, version 1
  • ARXIV : 1907.04385

Collections

Citation

Guillaume Ducoffe, Michel Habib, Laurent Viennot. Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension. SODA 2020 - ACM-SIAM Symposium on Discrete Algorithms, Jan 2020, Salt Lake City, United States. ⟨hal-02340382⟩

Share

Metrics

Record views

168

Files downloads

454