Guillaume Ducoffe

Michel Habib

Laurent Viennot

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

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.

Introduction

In this paper we present new results on exact diameter computation within several classes of unweighted (undirected) graphs with a geometric flavor. We recall that the diameter of an unweighted graph is the maximum number of edges on a shortest path. Beyond its many practical applications, this fundamental problem in Graph Theory has attracted a lot of attention in the fine-grained complexity study of polynomial-time solvable problems [START_REF] Abboud | Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs[END_REF][START_REF] Backurs | Towards tight approximation bounds for graph diameter and eccentricities[END_REF][START_REF] Borassi | Into the square: On the complexity of some quadratictime solvable problems[END_REF][START_REF] Cairo | New bounds for approximating extremal distances in undirected graphs[END_REF][START_REF] Chechik | Better approximation algorithms for the graph diameter[END_REF][START_REF] Dahlgaard | On the hardness of partially dynamic graph problems and connections to diameter[END_REF][START_REF] Ducoffe | A New Application of Orthogonal Range Searching for Computing Giant Graph Diameters[END_REF][START_REF] Evald | Tight Hardness Results for Distance and Centrality Problems in Constant Degree Graphs[END_REF][START_REF] Roditty | Fast approximation algorithms for the diameter and radius of sparse graphs[END_REF]. More precisely, for every n-vertex m-edge unweighted graph the textbook algorithm for computing its diameter runs in time O(nm). In a seminal paper [START_REF] Roditty | Fast approximation algorithms for the diameter and radius of sparse graphs[END_REF] this roughly quadratic running-time (in the size n + m of the input) was matched by a quadratic lower-bound, assuming the Strong Exponential-Time Hypothesis (SETH). We stress that for graphs with millions of nodes and edges, quadratic time is already prohibitive. The conditional lower-bound of [START_REF] Roditty | Fast approximation algorithms for the diameter and radius of sparse graphs[END_REF] also holds for sparse graphs i.e., with only m = O(n) edges [START_REF] Abboud | Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs[END_REF]. However it does not hold for many well-structured graph classes [START_REF] Abboud | Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs[END_REF][START_REF] Brandstädt | The algorithmic use of hypertree structure and maximum neighbourhood orderings[END_REF][START_REF] Bringmann | Multivariate analysis of orthogonal range searching and graph distances parameterized by treewidth[END_REF][START_REF] Corneil | Diameter determination on restricted graph families[END_REF][START_REF] Cabello | Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs[END_REF][START_REF] Coudert | Fully polynomial FPT algorithms for some classes of bounded clique-width graphs[END_REF][START_REF] Damaschke | Computing giant graph diameters[END_REF][START_REF] Ducoffe | A New Application of Orthogonal Range Searching for Computing Giant Graph Diameters[END_REF][START_REF] Eppstein | Diameter and treewidth in minor-closed graph families[END_REF][START_REF] Farley | Computation of the center and diameter of outerplanar graphs[END_REF][START_REF] Gawrychowski | Voronoi diagrams on planar graphs, and computing the diameter in deterministic Õ(n 5/3 ) time[END_REF][START_REF] Olariu | A simple linear-time algorithm for computing the center of an interval graph[END_REF]. Our work proposes some new advances on the characterization of graph families for which we can compute the diameter in truly subquadratic time.

Related work

Before we detail our contributions, we wish to mention a few recent (and not so recent) results that are most related to our approach.

Interval graphs. An early example of linear-time solvable special case for diameter computation is the class of interval graphs [START_REF] Olariu | A simple linear-time algorithm for computing the center of an interval graph[END_REF]. For every interval graph G and for any integer k, if we first compute an interval representation for G in linear-time [START_REF] Habib | Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing[END_REF] then we can compute by dynamic programming, for every vertex v, the contiguous segment of all the vertices at a distance ≤ k from v in G. It takes almost linear-time and it implies a straightforward quasi linear-time algorithm for diameter computation. More efficient algorithms for diameter computation on interval graphs and related graph classes were proposed in [START_REF] Corneil | Diameter determination on restricted graph families[END_REF]. Nevertheless we will show in what follows that interval orderings are a powerful tool for diameter computation on more general geometric graph classes.

Bounded-treewidth graphs. More recently, quasi linear-time algorithms for diameter computation on bounded-treewidth graphs were presented in [START_REF] Abboud | Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs[END_REF][START_REF] Bringmann | Multivariate analysis of orthogonal range searching and graph distances parameterized by treewidth[END_REF] with almost optimal dependency on the treewidth parameter. The cornerstone of these algorithms is the use of k-range trees in order to detect the furthest pairs that are disconnected by some small-cardinality separators. Since then a few other applications of k-range trees and, more generally, orthogonal range searching for diameter computation, have been presented in [START_REF] Ducoffe | A New Application of Orthogonal Range Searching for Computing Giant Graph Diameters[END_REF][START_REF] Ducoffe | Fast diameter computation within split graphs[END_REF]. In our work we uncover deeper connections between diameter computation and range searching techniques from computational geometry.

Planar graphs. Finally, in a recent breakthrough paper [START_REF] Cabello | Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs[END_REF], Cabello presented the first truly subquadratic algorithm for diameter computation on planar graphs (see also [START_REF] Gawrychowski | Voronoi diagrams on planar graphs, and computing the diameter in deterministic Õ(n 5/3 ) time[END_REF] for improvements on his work). For that he combined r-divisions: a recursive decomposition technique for planar graphs and other hereditary graph classes with sublinear balanced separators, with a clever use of additively weighted Voronoi diagrams. Cabello conjectured that his algorithm could be generalized to bounded-genus graphs. The long version of [START_REF] Gawrychowski | Voronoi diagrams on planar graphs, and computing the diameter in deterministic Õ(n 5/3 ) time[END_REF] indicates that their techniques could allow such a generalization if computing the diameter of a graph embedded onto a surface of genus g reduces to the planar case with O(g) holes in the regions of some r-division. Although it is known that such a graph can be decomposed into planar subgraphs by removing 2g shortest paths [START_REF] Kawarabayashi | Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs[END_REF][START_REF] Eppstein | Dynamic generators of topologically embedded graphs[END_REF], such reduction is not clear, and we could not find references formally supporting this. More recently, Li and Parter proposed a distributed algorithm for planar diameter which is based on metric compression [START_REF] Li | Planar diameter via metric compression[END_REF] and uses a VC-dimension argument to bound the number distance profiles with respect to a given subset of nodes. Following the basics of planar algorithms, we partly reuse rdivisions within our algorithms. However we replace the intricate use of Voronoi diagrams with a quite different approach that is based on some interval representations of the balls of a given radius in a graph. Our approach is also based on a VC-dimension argument but in a very different way than [START_REF] Li | Planar diameter via metric compression[END_REF]. In doing so, we can obtain truly subquadratic-time algorithms for diameter computation on bounded genus graphs (and more generally, on any proper minor-closed graph family) while avoiding a great deal of topological complications. Note that our approach works similarly for computing the radius whereas it not clear whether the Voronoi diagram approach does.

We stress that for the three aforementioned graph classes, the techniques used for computing their diameter are quite different from each other. Our work is a first step toward unifying all these previous results for unweighted graphs in a single framework (note that some of the aforementioned results also hold in the directed weighted case).

Our contributions

We study the parameterization of graph diameter by the VC-dimension of various hypergraphs. More precisely, a set Y is shattered by a hypergraph H if by intersecting Y with all hyperedges of H one obtains the power-set of Y . The VC-dimension of H is then defined as the largest cardinality of a subset shattered by H. This powerful notion was first introduced by Vapnik and Chervonenkis in [START_REF] Vapnik | On the uniform convergence of relative frequencies of events to their probabilities[END_REF]. Since then it has found applications in sampling complexity and machine learning, among other domains. We refer to [START_REF] Kranakis | The VC-dimension of set systems defined by graphs[END_REF] for early work on VC-dimension in graphs. In particular, the VCdimension of a graph G is defined as the VC-dimension of its closed neighbourhood hypergraph: whose hyperedges are the closed neighbourhoods of vertices in G. Graphs of bounded interval number and proper minor-closed graph classes are two examples of graph families with a constant upper-bound on their VC-dimension [START_REF] Kranakis | The VC-dimension of set systems defined by graphs[END_REF][START_REF] Chepoi | Covering planar graphs with a fixed number of balls[END_REF].

First example.

As an appetizer we first consider an n-vertex split graph with clique-number log O(1) n, that is a notouriously hard case for diameter computation [START_REF] Borassi | Into the square: On the complexity of some quadratictime solvable problems[END_REF]. Given such a split graph G with stable set S and maximal clique K, we can pre-process G in linear-time so as to partition the vertices of S into twin classes: with two vertices in S being called twins if and only if they have the same neighbourhood in K (e.g., see [START_REF] Coudert | Fully polynomial FPT algorithms for some classes of bounded clique-width graphs[END_REF]). If the VC-dimension of G is at most d then, by the Sauer-Shelah-Perles Lemma [START_REF] Sauer | On the density of families of sets[END_REF][START_REF] Shelah | A combinatorial problem; stability and order for models and theories in infinitary languages[END_REF] the number of twin classes is in O(|K| d ) = log O(d) n. Therefore, after some linear-time preprocessing, we are left with computing the diameter on a graph of polylogarithmic order! Unfortunately, such simple brute-force arguments are no longer sufficient for split graphs of arbitrary clique-size.

Overview of our techniques. In order to generalize our approach to any graph of constant VC-dimension, we use the central notion of spanning paths with low stabbing number. Chazelle and Welzl [START_REF] Chazelle | Quasi-optimal range searching in spaces of finite VC-dimension[END_REF] defined a spanning path for a hypergraph H as a total ordering of its vertex-set. The stabbing number of such a path is, up to 1, the maximum number of maximal intervals of which a hyperedge in H can be the union (we refer to Sec. 2 for a formal definition).

Assume for now that we are given a spanning path with stabbing number t for the closed neighbourhood hypergraph of G. Then in linear time, we can compute for every vertex v the ends of the O(t) intervals of which N G [v] is the union. We denote this set of intervals by I(v) in what follows. Then, in order to decide whether G has diameter at most two, it is sufficient to check whether for every vertex u we have v∈N G [u] I(v) = V . Since we only need to consider the ends of such intervals, this verification phase takes time O(deg G (u) • t) for a vertex of degree deg G (u), and so, O(tm) total time. Note that such running-time is always subquadratic if t is sublinear in n. Overall, we reduced the diameter-two problem to the computation of a spanning path with low stabbing number for the closed neighbourhood hypergraph.

Motivated by range searching problems, Chazelle and Welzl proved the existence of spanning paths with strongly sublinear stabbing number for every hypergraph of constant VC-dimension [START_REF] Chazelle | Quasi-optimal range searching in spaces of finite VC-dimension[END_REF]! Following this approach, we obtain our first main result in this paper: Theorem 1. For every d > 0, there exists a constant ε d ∈ (0; 1) such that in deterministic time Õ(mn1-ε d ) we can decide whether a graph of VC-dimension at most d has diameter two.

We stress that in contrast to Theorem 1, under the Strong Exponential-Time we cannot decide whether a general graph has diameter at most two in truly subquadratic time [START_REF] Roditty | Fast approximation algorithms for the diameter and radius of sparse graphs[END_REF].

On our way to prove Theorem 1 our main difficulty was to show how to compute for a hypergraph H a spanning path of low stabbing number. Computing a spanning path of minimum stabbing number is NP-hard [START_REF] Bilo | On the crossing spanning tree problem. In Approximation, Randomization, and Combinatorial Optimization[END_REF]. However, there exist approximation algorithms for this problem that run in polynomial time [START_REF] Bilo | On the crossing spanning tree problem. In Approximation, Randomization, and Combinatorial Optimization[END_REF][START_REF] Har-Peled | Approximating Spanning Trees with Low Crossing Number[END_REF]. Their approximation ratio is logarithmic, that is fine for our applications. Unfortunately, the fastest known algorithms require us to solve a linear program. So far, the best known algorithms for this intermediate problem run in superquadratic time [START_REF] Cohen | Solving linear programs in the current matrix multiplication time[END_REF]. We show how to decrease the running-time of this part, at the price of a slightly increased stabbing number. For that, we carefully apply the deterministic algorithm resulting from [START_REF] Chazelle | Quasi-optimal range searching in spaces of finite VC-dimension[END_REF] to some arbitrary partition of H in subhypergraphs of sublinear size. This nice trick might be of independent interest. We thus state the following theorem where the size of a hypergraph is defined as the sum of its hyperedge cardinalities.

Theorem 2. For every d > 0, there exists a constant ε d ∈ (0; 1) such that in Õ(m + n 2-ε d ) deterministic time, for every n-vertex hypergraph H of VC-dimension at most d and size m, we can compute a spanning path of stabbing number Õ(n 1-ε d ).

Moreover,

ε d = 1 2 d+1 [c(d+1)-1]+1 for some universal constant c > 2.
From VC-dimension to distance VC-dimension. In order to go beyond Theorem 1, we need to consider a stronger notion of VC-dimension for graphs. The distance VC-dimension 1 of G is equal to the VC-dimension of its ball hypergraph: of which the hyperedges are all possible balls in G. Note that a bounded distance VC-dimension implies a bounded VC-dimension, but the converse a priori does not hold. Nevertheless, and perhaps surprisingly, there are still many classes of graphs with a constant distance VC-dimension. These classes include, among others: interval graphs, planar graphs [START_REF] Chepoi | Covering planar graphs with a fixed number of balls[END_REF] and, more generally, any proper minor-closed graph family(from Remark 3 in [START_REF] Chepoi | Covering planar graphs with a fixed number of balls[END_REF]), as well as graphs of bounded rank-width [START_REF] Bousquet | VC-dimension and Erdős-Pósa property[END_REF].

Theorem 3. There exists a Monte Carlo algorithm such that, for every positive integers d and k, we can decide whether a graph of distance VC-dimension at most d has diameter at most k. The running time is in Õ(k • mn 1-ε d ), where ε d ∈ (0; 1) only depends on d.

Eppstein proved in [START_REF] Eppstein | Diameter and treewidth in minor-closed graph families[END_REF] that for any constant k, we can decide in linear time whether the diameter of a planar graph is at most k. Our result can be seen as a generalization of his to any graph class of constant distance VC-dimension -but at the price of a superlinear running-time. Furthermore, our techniques also apply to superconstant diameters, say polylogarithmic in n, or even polynomial in n provided the exponent is in o(ε d ).

Our main technical contribution in this part is the efficient computation of spanning paths with strongly sublinear stabbing number for some dense hypergraphs of constant VC-dimension. More precisely, the -neighbourhood hypergraph of G has for hyperedges the balls of radius in G. For instance, the 1-neighbourhood hypergraph of G is exactly its closed neighbourhood hypergraph. In order to prove Theorem 3, we reduce the problem of deciding whether a graph has diameter at most k to the computation of a spanning path with low stabbing number for its (k -1)-neighbourhood hypergraph. In this sense, the proofs of Theorems 1 and 3 are very similar. However, an additional difficulty here is that we cannot have direct access to this (k -1)-neighbourhood hypergraph. Indeed, in the worst case all hyperedges of this hypergraph may have a cardinality in Ω(n), and then storing the hypergraph itself would already require quadratic space.

We overcome this issue by computing an ε-net [START_REF] Haussler | ε-nets and simplex range queries[END_REF][START_REF] Vapnik | On the uniform convergence of relative frequencies of events to their probabilities[END_REF] in order to partition the vertices of the graph in a small number of groups, with every two vertices in the same group having almost the same ball of radius k -1. By selecting only one vertex per group, we so reduce the number of hyperedges (i.e., balls of radius k -1) to be considered. Finally, once a spanning path was computed for this smaller hypergraph, for every unselected vertex we compute the symmetric difference between its ball of radius k -1 and the one of the unique vertex taken in its group. Our solution in order to do that efficiently is to first compute a spanning path with low stabbing number for the (k -2)-neighbourhood hypergraph. This is where the dependency on k occurs, as overall we will need to compute a spanning path for k -1 consecutive hypergraphs. Our algorithm is randomized and succeeds with high probability. The use of randomization comes from the ε-net construction. Although deterministic algorithms do exist for that [START_REF] Brönnimann | Product range spaces, sensitive sampling, and derandomization[END_REF], it is not clear whether they can be used as efficiently as the simple sampling technique of the randomized algorithm. We leave open the question of finding a deterministic variant of Theorem 3.

We note that this above technique can be applied under slightly weaker hypothesis than the one we state in Theorem 3. For instance, Nešetřil and Ossona de Mendez proved that for all nowhere dense graph classes (i.e., a broad generalization of proper minor-closed graph classes and bounded-degree graphs), for any graph in the class and for any constant k, the VC-dimension of the k-neighbourhood hypergraph is constantly upper-bounded [START_REF] Nešetřil | Structural sparsity[END_REF]. It allows us to derive the following weaker version of our Theorem 3: Theorem 4. Let G be a class of nowhere dense graphs. There exists a Monte Carlo algorithm such that, for every constant k = O(1), for any graph in G we can decide whether its diameter is at most k in time Õ(mn 1-ε G (k) ), for some constant ε G (k) ∈ (0; 1) that only depends on k.

Let us mention that under SETH, Theorem 4 is the best result that we can hope for nowhere dense graph classes. Indeed, bounded-degree graphs are nowhere dense and, under SETH, we cannot compute their diameter in truly subquadratic time even if it is in ω(log n) [START_REF] Evald | Tight Hardness Results for Distance and Centrality Problems in Constant Degree Graphs[END_REF].

We conjecture that on every graph family of constant distance VC-dimension, we can compute the diameter in truly subquadratic time. Our next main result shows the conjecture to be true for any monotone graph family with strongly sublinear balanced separators, a.k.a the graphs of polynomial expansion [START_REF] Dvorak | Strongly sublinear separators and polynomial expansion[END_REF].

Theorem 5. Let G be a monotone graph class with strongly sublinear balanced separators. Then there exists a Monte Carlo algorithm such that, for every d > 0, we can compute the diameter of any graph in G of distance VC-dimension at most d in time Õ(n2-ε G (d) ), for some constant ε G (d) ∈ (0; 1) that only depends on d.

Let us recall that H-minor free graphs have a constant distance VC-dimension from Remark 3 in [START_REF] Chepoi | Covering planar graphs with a fixed number of balls[END_REF] (see also [START_REF] Bousquet | VC-dimension and Erdős-Pósa property[END_REF]), and that they all have strongly sublinear balanced separators [START_REF] Alon | A separator theorem for nonplanar graphs[END_REF][START_REF] Kawarabayashi | A separator theorem in minor-closed classes[END_REF][START_REF] Wulff-Nilsen | Separator theorems for minor-free and shallow minor-free graphs with applications[END_REF]. Therefore, as an important consequence of Theorem 5, we get a truly subquadratic-time algorithm for computing the diameter on all the proper minor-closed graph classes.

It might be tempting, in the above Theorem 5, to drop the assumption that the distance VCdimension must be bounded. Unfortunately, this cannot be done assuming SETH. Indeed, there is also an equivalence between the graphs of strongly sublinear treewidth and those monotone graph classes with strongly sublinear balanced separators [START_REF] Dvořák | Treewidth of graphs with balanced separations[END_REF]; however it follows from [START_REF] Abboud | Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs[END_REF] that under SETH, we cannot compute the diameter in truly subquadratic time already for n-vertex graphs of treewidth ω(log n). Conversely, not all graph classes with constant distance VC-dimension have strongly sublinear separators. This can be seen, e.g., with interval graphs.

The speed-up of Theorem 5 follows from a faster computation of spanning paths for the neighbourhood hypergraphs. More precisely, we explain how to compute a spanning path for the 2kneighbourhood hypergraph of G from a spanning path of its k-neighbourhood hypergraph. Note that in doing so, we only need to consider logarithmically many intermediate hypergraphs in order to compute such spanning path. Our approach for that consists in computing a first (suboptimal) representation of the 2k-neighbourhood of every vertex. Then, as for Theorem 3, we partition the vertices into a small number of groups and we select a unique vertex in each group. The suboptimal representations are used at the end of the algorithm in order to compute, for every unselected vertex, the symmetric difference between its ball of radius 2k and the one of the unique vertex taken in its group. So the problem becomes how to compute efficiently these suboptimal representations?

For that, we use a rather classical divide-and-conquer approach. Federickson [START_REF] Federickson | Fast algorithms for shortest paths in planar graphs, with applications[END_REF] proved that a planar graph can be edge-covered with O(n/r) subgraphs of order at most r such that at most O( √ r) vertices of each subgraph can be contained in another subgraph of this decomposition. His construction directly follows from the planar separator theorem of Lipton and Tarjan [START_REF] Lipton | A separator theorem for planar graphs[END_REF], and as such it can be easily adapted for any monotone graph family with sublinear balanced separators [START_REF] Henzinger | Faster shortest-path algorithms for planar graphs[END_REF] 2 . For illustrating our method, we now focus in this introduction on the planar case. We can first compute, for some well-chosen r = n γ , γ ∈ (0; 1), a decomposition as described above. For every two vertices in a same subgraph, we can check whether they are at distance at most 2k by checking whether their balls of radius k intersect; assuming r is small enough, and we precomputed a spanning path with low stabbing number for the k-neighbourhood hypergraph, this phase can be implemented in order to run in truly subquadratic time. Then for every subgraph of the decomposition, we compute a breadth-first search from each of the O( √ r) boundary vertices that are also contained in another subgraph. Overall, there can only be O(n/ √ r) such boundary vertices, and so, it takes truly subquadratic time. Furthermore in doing so, we computed for every subgraph of the decomposition the O(r √ r) distances between the boundary vertices and all the others. For any vertex v that is not on the boundary, we observe that a vertex in another subgraph can be at a distance ≤ 2k from v if and only if it is at distance ≤ 2k -dist G (v, x) from some vertex x on the boundary (O( √ r) balls to be considered). Our strategy consists in computing a spanning path with low stabbing number for some "boundary hypergraph" whose hyperedges are the O(r √ r × (n/r)) = O(n √ r) balls that we need to consider. We encounter a similar problem as for Theorem 3 because storing this hypergraph may require superquadratic space. Fortunately, we can encode this hypergraph in a much more compact way by taking advantage of (i) the fact that we can only have O(n/ √ r) different centers for the balls, and (ii) that all the balls with a same center have a chain-like inclusion structure.

Although we keep the focus on computing the diameter, we shall stress in Sec. 2.4 that all our techniques can also be applied to radius computation (i.e., see Remark 1). Our algorithms almost need no particular information about the graph structure in order to be applied. In fact, we do not even need to compute the (distance) VC-dimension of the input graph! From the applicative point of view, this observation (further discussed in Sec. 2.4) is quite important. Indeed, computing the VC-dimension is W[1]-hard [START_REF] Downey | Parameterized learning complexity[END_REF] and LogNP-hard [START_REF] Papadimitriou | On limited nondeterminism and the complexity of the VC dimension[END_REF].

Organization of the paper

In Sec. 2 we formally introduce the concepts of (distance) VC-dimension and stabbing number, along with some of their basic properties. Then, we explain in Sec. 3 how to compute a spanning path with strongly sublinear stabbing number for a hypergraph of constant VC-dimension (Theorem 2). As a direct application, we give a short proof of Theorem 1. Our techniques are generalized in Sec. 4 so as to prove Theorems 3 and 4. Finally, our main technical result (Theorem 5) is proved in Sec. 5. For that, we will need to recall some useful results on the graphs of polynomial expansion [START_REF] Dvorak | Strongly sublinear separators and polynomial expansion[END_REF]. We discuss some possible future work in Sec. 6.

Preliminaries

After recalling a few basic definitions about graphs and hypergraphs (Sec. 2.1 and 2.2) we introduce our framework for computing the diameter of a graph in Sec. 2.3 and 2.4.

Graphs and Diameter

For any undefined graph terminology, see [START_REF] Bondy | Graph theory[END_REF]. Throughout all this paper we only consider graphs that are undirected, unweighted and connected. For every graph G = (V, E), let n := |V | be its order and m := |E| be its size. We denote by N G (v) and

N G [v] := N G (v) ∪ {v} the open and closed neighbourhoods of vertex v, respectively. The degree of v is equal to |N G (v)| and is denoted by deg G (v) in what follows.
The length of a path is its number of edges, and the distance dist G (u, v) between u, v ∈ V is equal to the length of a shortest uv-path. For every v ∈ V and k ≥ 0, the k-neighbourhood of v, also known as the ball of center v and radius k, is defined as

N k G [v] = {u ∈ V | dist G (u, v) ≤ k}. For instance, N 1 G [v] is exactly the closed neighbourhood of v. The diameter of G is equal to diam(G) = max u,v∈V dist G (u, v).

Problem 1 (Diameter).

Input: A graph G = (V, E).

Output:

The diameter of G.

Theorem 6 ([57]

). Under the Strong Exponential-Time Hypothesis, we cannot decide whether a graph has diameter at most two in time O(mn 1-ε ), for any ε > 0.

Hypergraphs

More generally, a hypergraph is a pair H = (X, R) with X being the set of vertices and R ⊆ 2 X being the set of hyperedges. See also [START_REF] Berge | Graphs and hypergraphs[END_REF] for any undefined hypergraph terminology. Let n := |X|, m := q∈R |q| and r := |R| be the order, the size and the number of hyperedges of H, respectively. For every vertex x ∈ X, let

R x := {q ∈ R | x ∈ q}. The dual of H is the hypergraph H * := (R, X * ), where X * := {R x | x ∈ X}.
In particular, H and H * * are isomorphic.

Several hypergraphs can be related to a graph G:

• The closed neighbourhood hypergraph, denoted by N 1 (G), has vertex-set X = V and hyperedge- set R = {N G [v] | v ∈ V };
• More generally, for every fixed ≥ 0, the -neighbourhood hypergraph of G is defined as

N (G) = (V, {N G [v] | v ∈ V }).
We stress that N (G) and its dual N * (G) are isomorphic [START_REF] Bousquet | VC-dimension and Erdős-Pósa property[END_REF].

• Finally, the ball hypergraph of G, simply denoted by B(G), has for hyperedges the balls of all possible centers and radii in G. Equivalently, B(G) = ≥0 N (G).

VC-dimension

Let H = (X, R) be a fixed hypergraph. A subset Y ⊆ X is shattered by H if, for every Y ⊆ Y , there exists a hyperedge q ∈ R such that Y ∩ q = Y . Then, the Vapnik-Chervonenkis dimension of H (abbreviated in what follows to VC-dimension) is the largest cardinality of a shattered subset.

Similarly, the dual VC-dimension of H is the VC-dimension of its dual H * . We will often use the following (easy) properties in our analysis:

Lemma 1 (Sauer-Shelah-Perles, [START_REF] Sauer | On the density of families of sets[END_REF][START_REF] Shelah | A combinatorial problem; stability and order for models and theories in infinitary languages[END_REF]). Every n-vertex hypergraph of VC-dimension at most d has O(n d ) hyperedges.

Lemma 2 ([18]

). Every hypergraph of VC-dimension d has dual VC-dimension at most 2 d+1 .

Lemma 3 ([46]

). For every hypergraph

H = (X, R) and Y ⊆ X, let R[Y ] = {q ∩ Y | q ∈ R}. Then, the VC-dimension of H[Y ] := (Y, R[Y ]) is at most the VC-dimension of H.
VC-dimension for graphs. The VC-dimension of a graph G is defined as the VC-dimension of its closed neighbourhood hypergraph N 1 (G). For instance, K h -minor free graphs (and so, H-minor free graphs for any H of order at most h) have VC-dimension at most h -1 [START_REF] Anthony | The Vapnik-Chervonenkis dimension of a random graph[END_REF]. Every k-interval graph has VC-dimension in O(k log k) [START_REF] Ducoffe | Fast diameter computation within split graphs[END_REF]. Other classes of constant VC-dimension -at most three -are unit disk graphs, chordal bipartite graphs, C 4 -free bipartite graphs, graphs of girth at least five and undirected path graphs [START_REF] Bousquet | Identifying codes in hereditary classes of graphs and VC-dimension[END_REF].

The distance VC-dimension of a graph G is defined as the VC-dimension of its ball hypergraph B(G). Chepoi, Estellon and Vaxès proved in [START_REF] Chepoi | Covering planar graphs with a fixed number of balls[END_REF] that planar graphs have distance VC-dimension at most 4, and remarked that more generally every K h -minor free graph has distance VC-dimension at most h -1. Bousquet and Thomassé proved in [START_REF] Bousquet | VC-dimension and Erdős-Pósa property[END_REF] that graphs of bounded distance VC-dimension also generalize graphs of bounded rankwidth. Indeed, every graph of rankwidth k has distance VC-dimension at most 3 • 2 k+1 + 1. For purpose of illustration, we next adapt a proof from [START_REF] Bousquet | Identifying codes in hereditary classes of graphs and VC-dimension[END_REF] in order to show that interval graphs have distance VC-dimension at most two:

Lemma 4. Every interval graph has distance VC-dimension at most 2.

Proof. Let G = (V, E) be an interval graph. We fix an interval model for G. For every v ∈ V , let

I(v) = [a v , b v ]
be the corresponding interval in the representation. Suppose now by contradiction that there is a set

S = {v 1 , v 2 , v 3 } that is shattered by B(G). W.l.o.g., a v 1 < a v 2 < a v 3 . Since S is shattered, there exist some u ∈ V and k ≥ 0 such that N k G [u] ∩ S = {v 1 , v 3 }. But then, let I k-1 (u) := w∈N k-1 G [u] I(w) be the contiguous segment of all the vertices at a distance ≤ k -1 from u. Note that I k-1 (u) ∩ I(v 2 ) = ∅ because we assume that v 2 / ∈ N k G [u].
In this situation, either

I k-1 (u) ⊆] -∞, a v 2 [ or I k-1 (u) ⊆]b v 2 , ∞[ where ]x, y[ = [x, y] \ {x, y}
denotes the open interval between x and y. In fact we must have

I k-1 (u) ⊆]b v 2 , ∞[ because otherwise, I k-1 (u) ∩ I(v 3 ) = ∅ and so, v 3 / ∈ N k G [u], a contradiction. Since I k-1 (u) ∩ I(v 1 ) = ∅, it implies that b v 1 > b v 2 , and so, I(v 2 ) ⊆ I(v 1 ). As a result we have N G [v 2 ] ⊆ N G [v 1 ]. But then, for any w ∈ V and ≥ 1, we have v 2 ∈ N G [w] =⇒ v 1 ∈ N G [w]
. The latter contradicts our hypothesis that S is shattered.

Stabbing number and applications to Diameter

A spanning tree of H = (X, R) is a tree T whose node-set is exactly X. The stabbing number of such spanning tree T is the least k such that, for every hyperedge q ∈ R, there exist at most k edges uv ∈ E(T ) such that |q ∩ {u, v}| = 1 (we also say that uv is stabbed by q). Given a set q ⊆ X, we let

E T (q) = {uv ∈ E(T ) | u ∈ q, v /
∈ q} of all edges stabbed by q. Finally, the stabbing number of H is the minimum stabbing number over its spanning paths. Indeed, as noted in [START_REF] Chazelle | Quasi-optimal range searching in spaces of finite VC-dimension[END_REF], every spanning tree T can be transformed into a spanning path of stabbing number at most twice bigger than for T . Therefore, there is essentially no loss of generality in restricting ourselves to spanning paths.

Lemma 5 ([18]

). Every n-vertex hypergraph of dual VC-dimension d has stabbing number Õ(n 1-1 d ).

Overall it follows from Lemmata 2 and 5 that any n-vertex hypergraph of VC-dimension at most d has strongly sublinear stabbing number in Õ(n

1-1 2 d+1
). We stress that the proof of Lemma 5 is constructive but that it cannot be transformed into a truly subquadratic-time algorithm. Efficient computations of spanning paths with sublinear stabbing number -or related data structures -were proposed for many special cases from computational geometry [START_REF] Chan | Optimal partition trees[END_REF][START_REF] Matoušek | Spanning trees with low crossing number[END_REF][START_REF] Welzl | On spanning trees with low crossing numbers[END_REF].

Problem 2 (f -Approx Stabbing Number).

Input: A hypergraph H = (X, R) of VC-dimension at most d.

Output: A spanning path P of stabbing number at most Õ(n

1-1 f (d) ) and, for every q ∈ R, the set E P (q) = {uv ∈ E(P ) | u ∈ q, v /
∈ q} of all edges stabbed by q.

For simplicity of exposition, we will assume throughout the remainder of this paper that the VC-dimension of all the hypergraphs considered is part of the input. However in practice, we can easily weaken this assumption as follows. Given some "guess" d on the VC-dimension of the input, we can modify our proposed solutions so that they either output a spanning path whose stabbing number is at most Õ(n

1-1 f (d) )
, for some function f , or conclude that the VC-dimension of the input is larger than d. By dichotomic search, we so can compute some minimum d * such that, for any d ≥ d * , our algorithms always output a spanning path of stabbing number Õ(n

1-1 f (d)
). We stress that d * is at most the VC-dimension of G, but that it can be much smaller in practice.

Reduction from diameter computation. We now recall the following simple but beautiful approach that we use in order to solve Diameter on graphs of constant VC-dimension. Proof. Let us first compute a spanning path P of stabbing number at most Õ(n

1-1 f (d) ) for N k-1 (G).
By the hypothesis, it takes O(T (n, m)) time. For every v ∈ V we can compute from

E P (N k-1 G [v]) a set I k-1 (v) of t v intervals, where |E P (N k-1 G [v])|-1 ≤ t v ≤ |E P (N k-1 G [v])|+1, such that I k-1 (v) = N k-1 G [v]. This preprocessing phase takes time O(|E P (N k-1 G [v])|) = Õ(n 1-1 f (d) )
, and so, Õ(n

2-1 f (d)
) total time. Then in order to decide whether diam(G) ≤ k, we are left to decide whether for every

u ∈ V we have v∈N G [u] I k-1 (v) = V . For that, it suffices to collect the Õ(deg G (u) • n 1-1 f (d) ) ends of the intervals in v∈N G [u] I k-1 (v)
, and then to order them lexicographically. As a result, this last verification phase can be done in total time Õ(mn

1-1 f (d) ).
Remark 1. The radius of a graph G is equal to rad(G) = min u∈V max v∈V dist G (u, v). Under the Hitting Set conjecture, we cannot compute the radius of a graph in truly subquadratic-time [START_REF] Abboud | Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs[END_REF]. We here observe that we can easily modify the framework of Lemma 6 in order to decide whether a graph has radius at most k. Indeed, for that it suffices to check whether there exists at least one vertex u such that v∈N G

[u] I k-1 (v) = V .
Our main task in the remainder of this article will be to solve f -Approx Stabbing Number efficiently on -neighbourhood hypergraphs, for some increasing function f . Then, we can apply Lemma 6 in order to efficiently solve Diameter.

Computation of Spanning paths with low Stabbing Number

We prove in this section our first main result in the paper, whose statement is reminded below: Theorem 1. For every d > 0, there exists a constant ε d ∈ (0; 1) such that in deterministic time Õ(mn 1-ε d ) we can decide whether a graph of VC-dimension at most d has diameter two.

We will need the following result in our proofs:

Lemma 7 ([18]

). There is a deterministic polynomial-time algorithm that outputs, for every nvertex hypergraph H of VC-dimension at most d, a spanning path of stabbing number O(n 1-1/2 d+1 log n).

This above lemma is a consequence of Theorem 4.3 in [START_REF] Chazelle | Quasi-optimal range searching in spaces of finite VC-dimension[END_REF] and the discussion about the complexity of the algorithm resulting from their proof. We note that their result applies to infinite range spaces too, with the initial step in their proof reducing to the finite case. In order to derive Lemma 7 from [START_REF] Chazelle | Quasi-optimal range searching in spaces of finite VC-dimension[END_REF], we use the bound on the dual VC-dimension resulting from Lemma 2 and the fact that no initial step is required as we start from a finite range space. Better randomized algorithms can be obtained through the approximation results in [START_REF] Bilo | On the crossing spanning tree problem. In Approximation, Randomization, and Combinatorial Optimization[END_REF][START_REF] Har-Peled | Approximating Spanning Trees with Low Crossing Number[END_REF]. They are expressed for spanning trees but easily convert to paths as previously noted. The algorithms in [START_REF] Bilo | On the crossing spanning tree problem. In Approximation, Randomization, and Combinatorial Optimization[END_REF][START_REF] Har-Peled | Approximating Spanning Trees with Low Crossing Number[END_REF] use LP relaxation and randomized rounding. It is not immediately clear if they can be derandomized using classical techniques. Indeed, the algorithm from [START_REF] Har-Peled | Approximating Spanning Trees with Low Crossing Number[END_REF] works by phases. During a phase, it needs to solve an ILP relaxation and then to apply some randomized rounding technique. In the worst case, this main phase is repeated O(log n) times. We observe that even by using the best known upper-bounds on the time complexity of linear programming [START_REF] Cohen | Solving linear programs in the current matrix multiplication time[END_REF], this overall process takes super-quadratic time. In what follows, we use the Sauer-Shelah-Perles Lemma (Lemma 1) in order to obtain better trade-offs between the running-time and the quality of our solution.

Theorem 2. For every d > 0, there exists a constant ε d ∈ (0; 1) such that in Õ(m + n2-ε d ) deterministic time, for every n-vertex hypergraph H of VC-dimension at most d and size m, we can compute a spanning path of stabbing number Õ(n 1-ε d ).

Moreover,

ε d = 1 2 d+1 [c(d+1)-1]+1 for some universal constant c > 2.
Proof. Let η ∈ (0; 1) to be fixed later in the proof. We arbitrarily partition the vertex-set X into subsets X 1 , X 2 , . . . , X p such that p = O(n 1-η ) and, for every 1

≤ i ≤ p, |X i | = O(n η ). Our aim is to apply Lemma 7 to the subhypergraphs H[X 1 ], H[X 2 ], . . . , H[X p ].
We stress that all these subhypergraphs can be constructed in total O(m)-time, as follows: we scan all the hyperedges q once in order to compute (q ∩ X i ) 1≤i≤p ; then, for every i, we use a linear-time sorting algorithm in order to suppress duplicated values in {q ∩ X i | q ∈ R}.

Claim 1. Given H[X 1 ], H[X 2 ], . . . , H[X p ],
we can compute a spanning path for H of stabbing number Õ(n

1-η 2 d+1
). Moreover, it takes O(n 1+η[c(d+1) -1] ) time for some universal constant c > 2.

Proof. By Lemma 3, every H[X i ] has VC-dimension at most d. This implies that H[X i ] has O(n ηd ) hyperedges (Lemma 1), and so it has size O(n η(d+1) ). Furthermore by Lemma 7 we can compute deterministically a spanning path of stabbing number Õ n

η 1-1 2 d+1
, in time O(n cη(d+1) ) for some universal constant c.

Let P 1 , P 2 , . . . , P p be the spanning paths that we obtain. We obtain a spanning path P for H by concatenating all the P i 's. For every 1 ≤ i ≤ p, we recall that the stabbing num-

ber of P i is in Õ n η 1-1 2 d+1
. Therefore by construction, the stabbing number of P is in

Õ p • n η 1-1 2 d+1 + p -1 = Õ n 1-η 2 d+1 .
Let P be the spanning path obtained with Claim 1. Finally, for every q ∈ R we compute the set E P (q) of all edges of P stabbed by q, in total O(m)-time, simply by scanning once all the hyperedges. The total running-time is in

O(m + p • n cη(d+1) ) = O(m + n 1+η[c(d+1)-1]
). Overall, we achieve a good trade-off between running-time and approximation factor if we have 2

-η 2 d+1 = 1 + η[c(d + 1) -1]. Therefore we set η = 1 c(d+1)+ 1
We observe that our analysis could be easily improved in some particular cases, e.g., for all hypergraphs that are isomorphic to their dual.

We are now ready to prove the main result in this section:

Proof of Theorem 1. We apply Theorem 2 to the closed neighbourhood hypergraph of G. Then, the result follows from Lemma 6 applied to the function f : d → 1/ε d .

Bounded Diameter with ε-nets

For graphs of bounded distance VC-dimension we now generalize Theorem 1 from the previous section to larger values for the diameter.

Theorem 3. There exists a Monte Carlo algorithm such that, for every positive integers d and k, we can decide whether a graph of distance VC-dimension at most d has diameter at most k. The running time is in Õ(k • mn 1-ε d ), where ε d ∈ (0; 1) only depends on d.

Our proof crucially relies on the concept of ε-net. We recall that for a hypergraph H = (X, R), a subset Y ⊆ X is called an ε-net if, for every q ∈ R, we have |q| ≥ εn =⇒ Y ∩ q = ∅. Lemma 8 ([42,[START_REF] Vapnik | On the uniform convergence of relative frequencies of events to their probabilities[END_REF]). For every hypergraph of VC-dimension at most d, any random subset of size

Ω d ε log 1 εδ is an ε-net with probability 1 -δ.
We will also need the following result: [START_REF] Chazelle | Quasi-optimal range searching in spaces of finite VC-dimension[END_REF]). For every hypergraph H = (X, R), let R := {q∆q | q, q ∈ R} be the set of symmetric differences between hyperedges. If H has VC-dimension at most d then, Ĥ := (X, R) has bounded VC-dimension.

Lemma 9 ([
We observe that no explicit upper bound on the VC-dimension of Ĥ was stated in [START_REF] Chazelle | Quasi-optimal range searching in spaces of finite VC-dimension[END_REF]. Nevertheless it can be easily deduced from their proof that it is in O(d log d) (see also [START_REF] Eisenstat | The VC dimension of k-fold union[END_REF]).

The following partition lemma which derives from the two above lemmata is the cornerstone of our algorithm.

Lemma 10. Let G = (V, E) be a graph of distance VC-dimension at most d, and let S be any random subset of size Θ(d/ε). Then w.h.p., for every ≥ 0 and for every u, v ∈ V such that

N G [u] ∩ S = N G [v] ∩ S, we have | N G [u]∆N G [v] | = Õ(εn). Proof. Let R = { N 1 G [x]∆N 2 G [y] |
x, y ∈ V and 1 , 2 ≥ 0} be the set of the symmetric differences between the balls of G. Since G has distance VC-dimension at most d then, by Lemma 9, the hypergraph Ĥ = (V, R) has VC-dimension in O(d log d). Then by Lemma 8, w.h.p. S is an ε-net for Ĥ. Therefore, for every ≥ 0 and for every u

, v ∈ V , | N G [u]∆N G [v] | > εn =⇒ (N G [u]∆N G [v]) ∩ S = ∅. We stress that (N G [u]∆N G [v]) ∩ S = ∅ =⇒ N G [u] ∩ S = N G [v] ∩ S.
This above partition lemma will be useful in order to group the vertices in a small number of groups, with every two vertices in a group having almost the same ball of radius . Here there is a trade-off between the number of groups (that we upper-bound by using the Sauer-Shelah-Perles Lemma) and, for every two vertices in the same group, the maximum number of vertices in which their respective balls of radius can differ.

More precisely, our approach in the next two sections can be summarized as follows:

1. We compute a spanning path P k for N k (G) of low average stabbing number, with the latter being equal to

1 n • v∈V |E P k (N k G [v])|;
2. Then, we compute an ε-net, for some well-chosen ε, and in doing so we partition the vertex-set into p(ε) disjoint groups V 1 , V 2 , . . . , V p(ε) . For every j we select a unique v j ∈ V j . We restrict ourselves to

H k := (V, {N k G [v j ] | 1 ≤ j ≤ p(ε)}).
We compute a spanning path P k of low stabbing number for this subhypergraph.

3. We observe that if P k is a spanning path of stabbing number t for H k , then it is also a spanning path of stabbing number t + O(εn) for N k (G). Finally, for every 1 ≤ j ≤ p(ε), we consider the unselected vertices u ∈ V j \ {v j } sequentially. We compute the set of all the edges in E(P k ) that are stabbed by

N k G [u]. For that, it suffices to compute the O(εn) vertices of N k G [u]∆N k G [v j ].
We do so efficiently by using the auxiliary spanning path P k .

We next give a first application of our approach (we will give another such application in the proof of Theorem 5).

Proof of Theorem 3. Let ε d be the constant of Theorem 2. We shall prove the following claim by finite induction: Claim 2. For every 1 ≤ i ≤ k -1, we can compute a spanning path of stabbing number Õ(n 1-ε d ) for N i (G). Moreover, it can be done in time

Õ(i • mn 1-ε d ).
The proof of Theorem 3 will follow from this claim and Lemma 6 by taking i = k -1. Proof. By Theorem 2, the claim is true for the base case i = 1. Assume by our induction hypothesis that the claim holds for i -1. We divide the remainder of the proof into two subclaims. Subclaim 1. Let P i-1 be a spanning path of stabbing number t for N i-1 (G). We can transform P i-1 into a spanning path P i for N i (G), such that v∈V

|E P i (N i G [v])| = O(tm)
. Moreover, the transformation takes time O(tm).

Proof. Let u ∈ V . Then in time O(deg G (u) • t), we can collect the edge-sets

E P i-1 (N i-1 G [w]
) of all the edges of P i-1 that are stabbed by w, for w ∈ N G [u]. We compute from these edge-sets a (suboptimal) representation of

N i G [u] into O(deg G (u) • t) intervals of P i-1 . • Subclaim 2. Let P i be a spanning path for N i (G), such that v∈V |E P i (N i G [v])| = O(tm). Then, in time Õ((n 1-ε d + t) • m), we can compute a spanning path P i of stabbing number Õ(n 1-ε d ).
Proof. Let ε := Θ(n -ε d ). We perform a breadth-first search from every vertex in some random subset S of cardinality Õ(d/ε) = Õ(n ε d ). In doing so we define an equivalence relation

∼ on V such that u ∼ v ⇐⇒ def N i G [u] ∩ S = N i G [v] ∩ S.
We so partition V into some groups V 1 , V 2 , . . . , V p . Since by the hypothesis G has distance VC-dimension at most d then, by Lemma 1 we have p = O(|S| d ) = Õ(n ε d d ). Furthermore by Lemma 10, we have w.h.p.

u ∼ v =⇒ | N i G [u]∆N i G [v] | = Õ(εn) = Õ(n 1-ε d ).
The algorithm now proceeds as follows:

1. For every 1 ≤ j ≤ p, we select a unique v j ∈ V j , and then we start a breadth-first search from this vertex. Since p = Õ(n ε d d ) and we have ε d 1/d, this phase can be implemented in time Õ(mn ε d d ) = õ(mn 1-ε d ), that is truly subquadratic.

Let R

i := {N i G [v j ] | 1 ≤ j ≤ p},
and let H i := (V, R i ). Note that since H i ⊆ B(G), the VC-dimension of H i is at most d. Furthermore, the order and size of H i are, respectively, n and m i := O(pn) = Õ(n 1+ε d d ). By Theorem 2, we can compute a spanning path P i for H i of stabbing number Õ(n

1-ε d ) in time Õ(m i + n 2-ε d ) = Õ(n 1+ε d d + n 2-ε d ) = Õ(n 1-ε d m).
3. We observe that P i is a spanning path of N i (G) of stabbing number:

Õ(n 1-ε d ) + max 1≤j≤p max u∈V j \{v j } | N i G [u]∆N i G [v j ] | = Õ(n 1-ε d ).
We are now left with computing, for every 1 ≤ j ≤ p and u ∈ V j \ {v j }, the set

E P i (N i G [u]
) of all the edges stabbed by the ball of radius i centered at u. For that, since we are already given

E P i (N i G [v j ]), it suffices to compute N i G [u]∆N i G [v j ].
We proceed in three steps:

• By our hypothesis, we computed a spanning path

P i for N i (G), such that u∈V |E(N i G [u])| = O(tm). Then, we can compute from P i a (suboptimal) representation I i (u) of N i G [u] into O(|E P i (N i G [u])|) intervals.
In doing so, we also compute within the same amount of time a representation

I i (u) of V \ N i G [u] into O(|E P i (N i G [u]
)|) intervals of P i . Overall this step takes total time Õ(tm).

• Let σ i : V → V (P i ) be the permutation that maps every vertex to its position in the spanning path P i . For every 1 ≤ j ≤ p, we construct two balanced binary search trees whose items are, respectively,

{σ i (x) | x ∈ N i G [v j ]} and {σ i (y) | y / ∈ N i G [v j ]}. Overall, this takes total time Õ(np) = Õ(n 1+ε d d ) = õ(mn 1-ε d ).
• Finally, let us again consider some u ∈ V j \{v j } for some j. For every interval from I i (u), we want to enumerate the vertices of V \ N i G [v j ] that lie on this interval. Since we stored all of V \ N i G [v j ] into a balanced binary search tree, this can be done in time O(log n) plus O(1) extra time per solution. In the same way, for every interval from I i (u), we enumerate the vertices of N i G [v j ] that lie on this interval. For a fixed u, the total time for this step is in Õ(

|I i (u)| + |I i (u)| + |N i G [u]∆N i G [v j ]| ) = Õ(|E P i (N i G [u])| + n 1-ε d ).
Therefore, this last step takes total time Õ(tm + n 2-ε d ).

• Now, by the induction hypothesis we get a spanning path of stabbing number Õ(n 1-ε d ) for N i-1 (G). By Subclaim 1 we transform such spanning path into a spanning path P i for N i (G), where

u∈V |E P i (N i G [u])| = Õ(mn 1-ε d ).
Finally, by Subclaim 2 we can use P i in order to compute, in time Õ(mn 1-ε d ), a spanning path P i of stabbing number Õ(n 1-ε d ). The above algorithm achieves proving that our claim holds for i.

Summarizing, by Claim 2 we can compute a spanning path of stabbing number Õ(n 1-ε d ) for the hypergraph N k-1 (G), in time Õ(k • mn 1-ε d ). By Lemma 6 it implies that we can also decide whether G has diameter at most k, and if so compute diam(G) exactly, in time Õ(k • mn 1-ε d ).

Application to nowhere dense graph classes

A closer look at the proof of Theorem 3 shows that it also holds if, instead of having bounded distance VC-dimension, there rather exists some constant d such that, for every 1 ≤ i ≤ k -1, the VC-dimension of the i-neighbourhood hypergraph is at most d (the latter value is sometimes called the distance-i VC-dimension of the graph [START_REF] Nešetřil | Structural sparsity[END_REF]). It has algorithmic implications for some special cases of sparse graphs. Namely, H is an r-shallow minor of a graph G if it can be obtained from some subgraph of G by the contraction of pairwise disjoint subgraphs of radius at most r [START_REF] Plotkin | Shallow Excluded Minors and Improved Graph Decompositions[END_REF]; a graph family G is termed nowhere dense if, for any r, there exists a graph H r which is not an r-shallow minor for any graph in G [START_REF] Nešetřil | Sparsity: graphs, structures, and algorithms[END_REF]. Of interest here is that, for any graph class G nowhere dense, and for any i, the distance-i VC-dimension of any graph in G is upper-bounded by some constant d i [START_REF] Nešetřil | Structural sparsity[END_REF]. By choosing d := max 1≤i≤k-1 d i , we thus obtain the following weaker version of Theorem 3 for nowhere dense graphs: Theorem 4. Let G be a class of nowhere dense graphs. There exists a Monte Carlo algorithm such that, for every constant k = O(1), for any graph in G we can decide whether its diameter is at most k in time Õ(mn 1-ε G (k) ), for some constant ε G (k) ∈ (0; 1) that only depends on k.

We left open whether there exists a truly subquadratic-time FPT algorithm for diameter computation on nowhere dense graph classes (i.e., with no dependency on k in the exponent).

Diameter computation in truly Subquadratic time

We finally improve the results of Theorem 3 for a more restricted family of graphs of bounded distance VC-dimension. Before that, we need to introduce a bit more of graph terminology. A class of graphs is called monotone if it is closed by taking subgraphs. For a connected n-vertex graph G, a separator is a subset S such that G \ S is disconnected. It is called balanced if every connected component of G\S has order at most 2n/3. Finally, a class of graphs has strongly sublinear balanced separator if every connected n-vertex graph in the class has a balanced separator of cardinality at most C • n α for some constants C and α < 1.

Theorem 5. Let G be a monotone graph class with strongly sublinear balanced separators. Then there exists a Monte Carlo algorithm such that, for every d > 0, we can compute the diameter of any graph in G of distance VC-dimension at most d in time Õ(n 2-ε G (d) ), for some constant ε G (d) ∈ (0; 1) that only depends on d.

We postpone the technical proof of this result to Sec. 5.2. Let us emphasize that Theorem 5 cannot be applied to all graph classes of bounded distance VC-dimension. For instance, we proved in Lemma 4 that the intervals graphs have distance VC-dimension at most two. However, there exist intervals graphs with no balanced separators of sublinear size. We give some interesting cases where Theorem 5 does apply in Sec. 5.1.

Finally, we say that a class of graphs G has polynomial expansion if there exists a polynomial p such that, for every r-shallow minor of a graph in G (cf. Section 4.1), the average degree is at most p(r). We want to stress that there is an equivalence between the monotone classes of graphs G with strongly sublinear balanced separators and those of polynomial expansion [START_REF] Dvorak | Strongly sublinear separators and polynomial expansion[END_REF]. In particular, the graphs in G have bounded degeneracy, and so, they are sparse (i.e., with m = O(n) edges). We will often use this property in what follows.

Application to H-minor free graphs

Let us now review some interesting classes where Theorem 5 does apply. Since planar graphs have distance VC-dimension at most four [START_REF] Bousquet | VC-dimension and Erdős-Pósa property[END_REF] then, it follows from the planar separator theorem of Lipton and Tarjan [START_REF] Lipton | A separator theorem for planar graphs[END_REF] that it is the case for planar graphs. Therefore, Theorem 5 gives us a new subquadratic-time algorithm for diameter computation on unweighted planar graphs, but with a slower running-time than for the algorithms presented in [START_REF] Cabello | Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs[END_REF][START_REF] Gawrychowski | Voronoi diagrams on planar graphs, and computing the diameter in deterministic Õ(n 5/3 ) time[END_REF]. More generally, the following separator theorem is from Alon et al.:

Lemma 11 ([2]
). Every K h -minor free graph has a balanced separator of cardinality O(h3/2 √ n). Moreover, such a separator can be found in O(n 3/2 ) time.

See also [START_REF] Kawarabayashi | A separator theorem in minor-closed classes[END_REF][START_REF] Wulff-Nilsen | Separator theorems for minor-free and shallow minor-free graphs with applications[END_REF] for various trade-offs between the size of the separator and the time that is needed in order to find it. We recall that K h -minor free graphs have distance VC-dimension at most h -1 [START_REF] Bousquet | VC-dimension and Erdős-Pósa property[END_REF]. By combining this result with Lemma 11, we so prove the following meta-theorem: Corollary 1. The diameter of a H-minor free graph can be computed in time Õ(n 2-ε H ), with a Monte Carlo algorithm, where ε H ∈ (0; 1) is a constant that only depends on H.

For most values of H this is the first known subquadratic-time algorithm for diameter computation on H-minor free graphs. In particular, this is the first known subquadratic algorithm for diameter computation on (unweighted) bounded-genus graphs to the best of our knowledge (see the planar graphs paragraph in the introduction).

Proof of Theorem 5

The remainder of this section is devoted to the proof of Theorem 5. We start by presenting, in a separate subsection, all the required background on r-divisions.

Algorithmic aspects of r-divisions

Throughout all this section, let G α,C be the class of all the graphs G such that, for every connected h-vertex subgraph of G, there exists a balanced separator of order at most C • h α . The following intermediate result is built upon a previous algorithm from Plotkin et al. [START_REF] Plotkin | Shallow Excluded Minors and Improved Graph Decompositions[END_REF]. Lemma 12 ([29]). For every n-vertex m-edge graph G ∈ G α,C , we can find a balanced separator of order O(n ). We will also use the following simple result: Lemma 13. Let G be a graph and S a balanced separator. We can bipartition the connected components of G \ S in two disjoint sets A and B such that min{|A|, |B|} ≤ 2n/3.

Proof. Let C 1 , C 2 , . . . , C k be the connected components of G \ S. We define i 0 := max{i | | j<i C j | ≤ 2n/3}. Let A := j<i 0 C j and B := j>i 0 C j . If |B ∪ C i 0 | ≤ 2n/3 then
we are done by setting A := A , B := B ∪ C i 0 . Thus, from now on let us assume that |B ∪ C i 0 | > 2n/3. Note that since S is a balanced separator, it implies that i 0 < k. Then, by the very definition of i 0 we also have

|A ∪ C i 0 | > 2n/3. Overall, |A | + 2|C i 0 | + |B | > 4n/3. Since |A | + |B | + |C i 0 | < n, we obtain |C i 0 | > n/3.
We are done by setting A := A ∪ B and B := C i 0 . Now, set β := 4+α 5 < 1 3 . By Lemma 12, for every n-vertex m-edge graph in G α,C we can compute a balanced separator of order O(n β ) in time O(n 1+β ). Following Federickson [START_REF] Federickson | Fast algorithms for shortest paths in planar graphs, with applications[END_REF], we define an r-division for an n-vertex graph G ∈ G α,C as follows:

• If n ≤ r then, we output G;

• Otherwise, let S be a balanced separator of cardinality O(n β ). Since S is balanced then, by Lemma 13 we can partition the connected components of G\S in two disjoint sets A and B of cardinality ≤ 2n/3. We end up computing an r-division for the induced subgraphs G[A ∪ S] and G[B ∪ S] separately. Note that since S is a separator, all edges of G are covered by these two subgraphs.

Therefore by construction, an r-division of a connected graph G is a collection of connected induced subgraphs of order at most r that cover all edges of G. We will use the terminology from [START_REF] Har-Peled | Approximation algorithms for polynomial-expansion and lowdensity graphs[END_REF]. In particular, the subgraphs in an r-division are termed clusters. A vertex is interior if it is contained in a unique cluster, otherwise it is a boundary vertex. Finally, if the sum of the orders of all the clusters is n + q then, we call q the excess.

The following result is essentially a reformulation of [41, Lemma 2.2].

Lemma 14 ([41]

). Set β := 4+α 5 . There exists a constant r 0 such that, for any n-vertex graph G ∈ G α,C and r ≥ r 0 , any r-division of G has an excess in O(n/r 1-β ).

Note that in our applications, we will choose r = n γ for some γ ∈ (0; 1) that only depends on β and on the distance VC-dimension.

It is easy to prove that an r-division can be computed in polynomial time [START_REF] Har-Peled | Approximation algorithms for polynomial-expansion and lowdensity graphs[END_REF]. Next we use the known connections between strongly sublinear separators and polynomial expansion [START_REF] Dvořák | On classes of graphs with strongly sublinear separators[END_REF] in order to bound the running-time by some truly subquadratic function. Proof. Let us assume that at the initialization step, n > r (otherwise, we are done). We claim that it is sufficient to prove that the total number of edges in the final clusters is in O(n). Indeed, if this is true for the final clusters then, this is also true for the intermediate clusters at any given step of the decomposition. In particular, every step runs in time O(n 1+β ). Furthermore, since we only consider balanced separators of sublinear cardinality, for every n above some constant the two induced subgraphs constructed have truly sublinear order (say, ≤ 3n/4). Therefore it takes O(log n) steps to decrease the order of all the subgraphs in this collection to less than r. This upper-bound on the number of steps proves, as claimed, that the total running time is in Õ(n 1+β ).

We are left proving that the total number of edges in the final clusters is indeed in O(n). For that, let us consider any of the clusters W i . Since G α,C is monotone, we have W i ∈ G α,C . Furthermore, every graph in G α,C must be O(1)-degenerate (e.g., see [START_REF] Dvořák | On classes of graphs with strongly sublinear separators[END_REF]Lemma 2 (b)] where the author proved a stronger result, namely that G α,C has polynomial expansion). It implies that W i has size O(|V (W i )|). Overall, if the total excess is q then, the total number of edges in the clusters is in O(n + q). By Lemma 14 we have q = O(n), and so the total number of edges is also in O(n).

Boundary Hypergraphs

Let G be a graph equipped with some r-division, and let be a positive integer. Roughly, our objective is to use the r-division in order to compute, for every vertex, a compact interval representation of its balls of radius . This leads us to the following natural object: Definition 7. Let Λ r be an r-division of a graph G, and let be a positive integer. Theboundary hypergraph H ,G (Λ r ) has for vertex-set V . Moreover, for every cluster W i ∈ Λ r and for every u, v ∈ V (W i ), if v is a boundary vertex and dist G (u, v) < , then the ball

N -dist G (u,v) G [v] is a hyperedge of H ,G (Λ r ).
To better understand this above construction, let W i be a cluster, let u ∈ V (W i ) be internal and let z / ∈ V (W i ). Then, since an r-division is also an edge-covering, we have dist G (u, z) ≤ if and only if there exists a boundary vertex v ∈ We stress that by Lemma 15, a boundary hypergraph may have a superlinear number of edges. Therefore, if we restrict ourselves to subquadratic-time computation, we cannot compute this hypergraph explicitly. Fortunately, we show next that this is not needed if one just wants to compute for this hypergraph a spanning path of low stabbing number.

V (W i ) such that dist G (u, v) + dist G (v, z) ≤ . Equivalently, we have z ∈ N -dist G (u,v) G [v].
Lemma 16. Set β := 4+α 5 , and let G ∈ G α,C have distance VC-dimension at most d. Then, there exists a constant ε d ∈ (0; 1) that only depends on d and such that, for any r-division Λ r , the stabbing number of H ,G (Λ r ) is in Õ(n 1-ε d ). Moreover, we can compute a spanning path reaching this upper bound in deterministic time Õ(n 2 /r 1-β + n 2-ε d r β ).

Proof. By construction, H ,G (Λ r ) is a subhypergraph of B(G), the ball hypergraph of G. Therefore, the VC-dimension of H ,G (Λ r ) is at most d. Let ε d be the constant of Theorem 2. In order to prove the result, we are left proving that we can adapt the algorithm of Theorem 2 so that it runs in time Õ(nm/r 1-β + n 2-ε d r β ) when it is given H ,G (Λ r ) as input. For that, let F be the set of the boundary vertices. We have that |F | is at most twice the excess, and so, by Lemma 14 we get |F | = O(n/r 1-β ).

1. We start with a breadth-first search from every vertex of F . This pre-processing phase takes time O(|F |m) = O(n 2 /r 1-β ). Furthermore, note that in doing so we computed all the pairs (v, t)

∈ F × [ ] such that N t G [v] is a hyperedge of H ,G (Λ r ).
2. Let η = 2 d+1 ε d . We arbitrarily partition the vertex-set V into subsets V 1 , V 2 , . . . , V p such that p = O(n 1-η ) and, for every 1 ≤ i ≤ p, |V i | = O(n η ). Furthermore, as explained in the proof of Theorem 2 (i.e., Claim 1), we can compute a spanning path of stabbing number Õ(n 1-ε d ) for H ,G (Λ r ) if we are given the subhypergraphs H 1 , H 2 , . . . , H p that are induced by V 1 , V 2 , . . . , V p respectively. It takes time Õ(n 1+η[c(d+1) -1] ) for some constant c, that is in Õ(n 2-ε d ).

In order to compute all the subhypergraphs H i , we could proceed by brute-force, as follows.

For every i and for any boundary vertex v, we read the vertices of V i by non-decreasing distance to v. Furthermore, if N t G [v] is a hyperedge of H ,G (Λ r ), then as soon as we exceed distance t all the vertices read so far are exactly N t G [v] ∩ V i . Overall, for a fixed boundary vertex v we could obtain this way up to O(|V i |) different subsets of order O(|V i |) each. But unfortunately, that would give us a time complexity in O(|F ||V i | 2 ) = O(n 1+2η /r 1-β ) for a given i, and so a total running time in O(n 2+η /r 1-β ). In order to lower this running-time, we proceed as follows.

(a) For every v ∈ F , we group all the vertices in V i at equal distance to v. We totally order this partition by increasing distance of its vertices to v. Doing so we get exactly n i := |V i | ordered groups (possibly, by adding some empty groups in the sequence), denoted

V 1 i (v), V 2 i (v), . . . , V n i i (v). Overall, this phase takes time O(|F ||V i |) = O(n 1+η /r 1-β
). (b) Then, we introduce a complex subprocedure in order to gradually remove the duplicates from the sets N t G [v] ∩ V i , for v ∈ F and t ≥ 0. For every j = 0 . . . n i , we map every boundary vertex v to j ≤j V j i (v). More precisely, we maintain some collection of different subsets of V i , denoted P j = V j,1 i , V j,2 i , . . . , V j,s i (j) i

(note that P j is a list of lists). For every v ∈ F we ensure that there is a unique t such that V j,t i = j ≤j V j i (v). Then, there is a pointer from vertex v to this t th subset (equivalently, for every list in P j , we store an auxiliary list of all the corresponding vertices of F ).

We will show next that it is easy to construct P j+1 from P j , but that the natural method for doing so might generate some duplicates. Roughly, by using in our analysis the Sauer-Shelah-Perles lemma, we prove that it is more efficient to remove duplicates at every single step rather than doing it only once at the end of the subprocedure.

We observe that initially for j = 0, there is a unique subset V 0,1 i = ∅. Furthermore if all the subsets V j,t i have been computed at step j, then we can compute those at step j + 1, as follows:

• For every v ∈ F , if we have V j,t i = j ≤j V j i (v), then we add a copy of V j+1 i (v) into some buffer b j+1 (t) and a pointer from v to this copy. It takes time O( v∈F |V j+1 i (v)|).

• Then, for every 1 ≤ t ≤ s i (j), we remove all the duplicated subsets in the buffer b j+1 (t). The new buffer that we get is denoted b j+1 (t). We can compute it by using partition refinement (e.g., see [START_REF] Habib | Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing[END_REF]), that takes time O( W ∈b j+1 (t) |W |) up to some O(|V i |)-time pre-processing. Overall the removal of all the duplicates, for all t, takes total time O(n η + v∈F |V j+1 i (v)|). Furthermore on our way to remove the duplicates, we also need to actualize the pointers between the boundary vertices and the buffer contents, that takes additional time O(|F |) = O(n/r 1-β ).

• For every 1 ≤ t ≤ s i (j), we can now refine V j,t i in |b j+1 (t)| new subsets. Every such subset has order O(n η ), and so this operation takes total time O(n η |b j+1 (t)|). Overall, we obtain a new collection of O( t |b j+1 (t)|) subsets. Furthermore, on our way to construct this collection, we can add a pointer from every boundary vertex v to one subset equal to j ≤j+1 V j i (v) (there may be duplicated subsets). By carefully using the pointers added between the boundary vertices and the buffer contents during the previous phases, this operation takes additional time O(|F |) = O(n/r 1-β ).

• Finally, since all the subsets in the new collection have order O(n η ), by using again partition refinement we can merge all the duplicated subsets in time

O(|V i | + n η • t |b j+1 (t)|) = O(n η • t |b j+1 (t)|).
We also need to actualize the pointers between the boundary vertices and the subsets, that takes total time O(|F |) = O(n/r 1-β ).

Let us upper bound s i (j). For that we stress that every subset V j,t i represents a different intersection of V i with a ball of G, hence of a hyperedge of B(G). Since B(G) has VCdimension at most d, by Lemma 3 so does its subhypergraph H i induced by V i . In particular, every V j,t i is a hyperedge of H i . By Lemma 1 we get that s i (j) = O(n ηd ). In the same way, since for a fixed t the |b j+1 (t)| new subsets that are obtained by refinement of V j,t i are pairwise different, we have |b j+1 (t)| ≤ s i (j + 1) = O(n ηd ). As a result, the passing from step j to step j + 1 takes time:

O v∈F V j+1 i (t) + n/r 1-β + n η • n ηd • n ηd = O v∈F V j+1 i (t) + n/r 1-β + n (2d+1)η .
There are O(n η ) loops, that gives us a total running time of:

O     v∈F n i j=1 V j+1 i (t)   + n 1+η /r 1-β + n (2d+2)η   = O v∈F n η + n 1+η /r 1-β + n 2(d+1)η = O n 1+η /r 1-β + n 2(d+1)η .
(c) Here the key observation is that j P j contains the intersection with V i of all the balls whose center is in F . We so computed a superset of order O(n (d+1)η ) (i.e., O(n ηd ) per loop) that contains all possible intersections between a hyperedge of H ,G (Λ r ) and V i . Since every subset in j P j represents the intersection of a hyperedge of B(G) with V i , and furthermore B(G) has VC-dimension at most d, then for simplicity we may replace H i by the slightly larger hypergraph H i of which these are the hyperedges (i.e., the hyperedges of H i are the intersections of V i with all the balls whose center is in F ). Note that in order to compute H i , it is sufficient to eliminate all the duplicated elements in this collection j P j , that takes total time O(n (d+2)η ).

The running-time is in Õ(n 1+η /r 1-β + n 2(d+1)η ) for any fixed i. Therefore, the total runningtime is in Õ(n 2 /r 1-β + n 1+[2(d+1)-1]η ). Recall (see Theorem 2 and its proof) that we have Õ(n 1+η[c(d+1)-1] ) = Õ(n 2-ε d ) for some constant c > 2. As a result, the running-time of this part is also in Õ(n 2 /r 1-β + n 2-ε d ).

3. By continuing the algorithm of Theorem 2 with the hypergraphs H 1 , H 2 , . . . , H p , we get a spanning path of H ,G (Λ r ) whose stabbing number is in Õ(n 1-ε d ). It remains to compute, for every hyperedge of H ,G (Λ r ), the set of the stabbed edges. For that, let v ∈ F be fixed. We add all the radii t such that N t G [v] is a hyperedge of H ,G (Λ r ) in a balanced binary research tree T v . Then, we scan all the edges xy of the spanning path. By symmetry let us assume that dist G (v, x) ≤ dist G (v, y). The edge xy is stabbed by all the hyperedges N

t G [v] such that dist G (v, x) ≤ t < dist G (v, y).
Then by using T v , after some pre-computation in time O(log n) every value t in the range [dist G (v, x); dist G (v, y)) can be enumerated in constant-time.

Overall, by Lemma 15 there are O(nr β ) edges, and so the construction of all the balanced binary research trees takes time Õ(nr β ). Scanning all the edges, for every boundary vertex, takes total time Õ(n 2 /r 1-β ). Any other operation corresponds to an edge of the spanning path that is stabbed by a hyperedge of H ,G (Λ r ), and as a result there can only be Õ(n

1-ε d )× O(nr β ) = Õ(n 2-ε d r β ) such operations.
Altogether combined, the running time of the algorithm is in Õ(n 2 /r 1-β + n 2-ε d r β ).

The algorithm

We are now ready to prove the main result of this section.

Proof of Theorem 5. By a classical dichotomic argument it is sufficient to prove that for any k, we can decide whether diam(G) ≤ k in truly subquadratic time. Furthermore in order to solve this decision problem, by Lemma 6 we are left with computing a spanning path of strongly sublinear stabbing number for the (k -1)-neighbourhood hypergraph. For that, let b 0 b 1 . . . b s-1 b s be the binary decomposition of k-1 (from the most significant to the less significant bit). Furthermore, for every 0 ≤ i ≤ s, let k i be the positive integer of binary decomposition b 0 b 1 . . . b i-1 b i . We will prove by finite induction that one can compute a spanning path of strongly sublinear stabbing number for the k i -neighbourhood hypergraph of G. More precisely, let ε d be the constant of Theorem 2. We will compute such spanning path of stabbing number Õ(n 1-ε d ) in Õ(n 2-ε ) time for some ε > 0. Note that since s = O(log k), that will indeed give us a truly subquadratic algorithm for deciding whether diam(G) ≤ k.

If i = 0, then b 0 = 1 and the result follows from Theorems 1 and 2. Thus from now on assume i > 0. We observe that k i = 2k i-1 + b i . Furthermore if b i = 1, then we explained in the proof of Theorem 3 (Subclaims 1 and 2) how to compute a spanning path of stabbing number Õ(n 1-ε d ) for N k i (G) from such spanning path for N k i -1 (G) = N 2k i-1 (G); it takes Õ(mn 1-ε d ) = Õ(n 2-ε d ) time, that is truly subquadratic. In order to complete the proof, we now adapt this algorithm of Theorem 3 so as to compute a spanning path with stabbing number Õ(n 1-ε d ) for N 2k i-1 (G) from such spanning path for N k i-1 (G). Specifically, let C and α < 1 be such that G ⊆ G α,C and set β := 4+α Claim 3. Let P i-1 be a spanning path of stabbing number Õ(n 1-ε d ) for N k i-1 (G). In Õ(n 2-ε d r + n 2 /r 1-β ) time, we can compute from P i-1 a spanning path P i for N 2k i-1 (G), such that

v∈V |E P i (N 2k i-1 G [v])| = Õ(n(r + n 1-ε d r β )).
Proof. By Lemma 2 we can compute an r-division, denoted Λ r , in time Õ(n 1+β ) = Õ(n 2 /r 1-β ). Then, we proceed as follows.

1. We first consider all the clusters W ∈ Λ r sequentially. For every x, y ∈ W we have dist G (x, y) ≤ 2k i-1 if and only if we have

N k i-1 G [x] ∩ N k i-1 G
[y] = ∅. Given a spanning path of stabbing number Õ(n 1-ε d ) for N k i-1 (G), this test can be easily done in time Õ(n 1-ε d ) (i.e., by sorting the ends of the Õ(n 1-ε d ) intervals on this spanning path that cover the balls N [u] that belong to a common cluster with u.

2. Let us now consider the 2k i-1 -boundary hypergraph H 2k i-1 ,G (Λ r ). By Lemma 16 we can compute a spanning path P i of stabbing number Õ(n 1-ε d ) for this hypergraph, in time Õ(nm/r 1-β + n 2-ε d r β ) = Õ(n 2 /r 1-β + n 2-ε d r β ). Let u ∈ V . There are two cases:

• Case u is a boundary vertex. Since N 2k i-1 G

[u] is a hyperedge of the boundary hypergraph, we have |E P i (N

2k i-1 G [u])| = Õ(n 1-ε d ) (already computed).
• Case u is an internal vertex. Let W ∈ Λ r be the unique cluster containing u, and set initially E P i (N

2k i-1 G
[u]) := ∅. For every boundary vertex v ∈ V (W ), if dist G (u, v) < 2k i-1

then, we add all of E P i (N

2k i-1 -dist G (u,v) G [v]) to E P i (N 2k i-1 G
[u]). Assuming there are b W boundary vertices in W , we obtain that |E P i (N

2k i-1 G [u])| = Õ(b W • n 1-ε d )
. Furthermore, this above set of stabbed edges defines a collection of intervals that covers exactly the balls

N 2k i-1 -dist G (u,v) G [v],
for the boundary vertices v ∈ V (W ). Denote this collection of intervals by I i (u), and its complementary by I i (u). By construction, every vertex on an interval of I i (u) is at a distance ≤ 2k i-1 to u; conversely, since Λ r is also an edgecovering, every vertex of N 2k i-1 G

[u] \ W must be on one of these intervals. As a result, in order to construct E P i (N

2k i-1 G
[u]), it suffices to update this set using the vertices of

N 2k i-1 G
[u] ∩ W that lie on some interval of I i (u). Note that in doing so, we can only modify the cardinality of E P i (N Overall, we obtain that u∈V |E P i (N

2k i-1 G [u])| = Õ(nr + n 1-ε d • W (b W • |V (W )|)) = Õ(nr + rn 1-ε d • W b W ).
Again we observe that W b W is at most twice the excess, and so by Lemma 14 W b W = O(n/r 1-β ). Therefore, u∈V |E P i (N

2k i-1 G [u])| = Õ(n(r + n 1-ε d r β )).
By combining Claim 3 with Subclaim 2, in Õ(n 2-ε d r + n 2 /r 1-β + n 1-ε d m) time we compute a spanning path of stabbing number Õ(n 1-ε d ) for N 2k i-1 (G), thereby completing the description of our algorithm. Overall, the running-time of our algorithm is optimized when we have n 2 /r 1-β = n 2-ε d r. As a result, a good choice is r = Θ(n ε d 2-β ). Finally, we stress that in this case, n 2-ε d r = n 2-1-1 2-β ε d is truly subquadratic, because β < 1 and so 1 -1 2-β > 0.

Open problems

We left open whether we can compute the diameter of all the graphs of constant distance VCdimension and unbounded diameter in truly subquadratic time. In order to prove that it is the case, we stress that by our Theorem 3 we only need to consider the graphs of large diameter, i.e., above some polynomial.

Another interesting direction could be to extend the constant distance VC-dimension framework to weighted graphs.

Finally, we observe that there exist graph families of unbounded (distance) VC-dimension for which we can compute the diameter very efficiently. For instance, the class of all the graphs with a universal vertex has unbounded VC-dimension. Such graphs are a particular case of dually chordal graphs, for which we know how to compute the diameter in linear time [START_REF] Brandstädt | Dually chordal graphs[END_REF]. We observe that the ball hypergraphs of dually chordal graphs also admit some nice characterizations. Thus, it would be very interesting to study whether a truly subquadratic algorithm for computing the diameter could be derived from some common property of dually chordal graphs and graphs of constant distance VC-dimension (say, a bounded fractional Helly number [START_REF] Matousek | Bounded VC-dimension implies a fractional Helly theorem[END_REF]).

Lemma 6 . 1 f

 61 Let G be a graph and k ≥ 2. If the hypergraph N k-1 (G) has VC-dimension at most d, and we can solve f -Approx Stabbing Number for N k-1 (G) in time T (n, m), then we can decide whether G has diameter at most k in time Õ(T (n, m) + mn 1-(d) ).

4+α 5 )

 5 in time O(mn 4+α 5 ) = O(n 2-1-α 5

Corollary 2 .

 2 Set β := 4+α 5 . Then, for any n-vertex m-edge graph G ∈ G α,C , we can compute an r-division in time Õ(n 1+β ).

Lemma 15 .

 15 Set β := 4+α 5 . Then, for any n-vertex graph G ∈ G α,C , and for any r-division Λ r , the -boundary hypergraph H ,G (Λ r ) has O(nr β ) hyperedges. Proof. For every W i ∈ Λ r , we create O(r • b i ) hyperedges, where b i denotes the number of boundary vertices in the cluster. We observe that W i ∈Λr b i is at most twice the excess. Then, by Lemma 14 we have O(r) × O(n/r 1-β ) = O(nr β ) hyperedges.

5 < 1 .

 51 The running time for computing the adequate spanning path will be Õ n 2-1-1 2-β ε d . We first prove the following intermediate result for any value r > 0 (we will use r = Θ(n ε d 2-β )):

  ). Furthermore by Lemma 14 we have W ∈Λr |W | = Θ(n), and so this step takes time Õ(n1-ε d ) × W ∈Λr O(|W | 2 ) = Õ(rn 1-ε d ) × W ∈Λr |W | = Õ(rn 2-ε d ).Overall for every u ∈ V , we computed all the vertices of N 2k i-1 G

2k i- 1 G

 1 [u]) by an O(|W |) = O(r).

Our definition of distance VC-dimension is slightly weaker than the one proposed in[START_REF] Bousquet | VC-dimension and Erdős-Pósa property[END_REF].

Note that Federickson proposed several refinements of his construction in[START_REF] Federickson | Fast algorithms for shortest paths in planar graphs, with applications[END_REF], some of which do use the fact that the input graph is planar. We will use in our proofs an even weaker version of his result than the one presented in this introduction.

d+1 -1 , and thenε d = η 2 d+1 = 1 2 d+1 [c(d+1)-1]+1 .

More generally, let G ⊆ Gα,C . We may choose any parameter β ∈ [α; 1) such that for all the graphs in G we can compute a balanced separator of size O(n β ) in truly subquadratic-time. For instance by Lemma 11, if G is proper minor-closed then we can set β = α = 1/2.

* This work was supported by project PN 19 37 04 01 "New solutions for complex problems in current ICT research fields based on modelling and optimization", funded by the Romanian Core Program of the Ministry of Research and Innovation (MCI) 2019-2022. This work was also supported by a grant of Romanian Ministry of Research and Innovation CCCDI-UEFISCDI. project no. 17PCCDI/2018.

† Supported by Inria Gang project-team, and ANR project DISTANCIA (ANR-17-CE40-0015).

‡ Supported by Irif laboratory from CNRS and Paris University, and ANR project Multimod (ANR-17-CE22-0016).