Massimo Cairo

Roberto Grossi

Romeo Rizzi

New Bounds for Approximating Extremal Distances in Undirected Graphs

We provide new bounds for the approximation of extremal distances (the diameter, the radius, and the eccentricities of all nodes) of an undirected graph with n nodes and m edges. First, we show under the Strong Exponential Time Hypothesis (SETH) of Impagliazzo, Paturi and Zane [JCSS01] that it is impossible to get a (3/2-ε)-approximation of the diameter or a (5/3 -ε)-approximation of all the eccentricities in O(m 2-δ ) time for any ε, δ > 0, even allowing for a constant additive term in the approximation. Second, we present an algorithmic scheme that gives a (2 -1/2 k )-approximation of the diameter and the radius and a (3 -4/(2 k + 1))approximation of all eccentricities in O(mn 1 k+1 ) expected time for any k ≥ 0. For k ≥ 2, this gives a family of previously unknown bounds, and approaches near-linear running time as k grows. Third, we observe a connection between the approximation of the diameter and the h-dominating sets, which are subsets of nodes at distance ≤ h from every other node. We give bounds for the size of these sets, related with the diameter.

Introduction

The diameter, the radius and the eccentricities of nodes are well-known extremal distances in graphs [START_REF] Kellogg | Computing extremal and approximate distances in graphs having unit cost edges[END_REF]. In an undirected graph G = (V, E), letting d(•, •) denote the distance among the nodes of G, the eccentricities are (v) = max u∈V d(v, u) for all nodes v ∈ V , the diameter is D = max v∈V (v) = max u,v∈V d(v, u), and the radius is r = min v∈V (v). (We postpone the discussion of directed graphs.) Their efficient computation is a basic problem in graphs [START_REF] Abboud | Subcubic equivalences between graph centrality problems, APSP and diameter[END_REF][START_REF] Aingworth | Fast estimation of diameter and shortest paths (without matrix multiplication)[END_REF][START_REF] Boitmanis | Fast and simple approximation of the diameter and radius of a graph[END_REF][START_REF] Borassi | Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs: With an application to the six degrees of separation games[END_REF][START_REF] Chechik | Better approximation algorithms for the graph diameter[END_REF][START_REF] Cygan | Algorithmic applications of Baur-Strassen's Theorem: Shortest cycles, diameter and matchings[END_REF][START_REF] Frischknecht | Networks cannot compute their diameter in sublinear time[END_REF][START_REF] Magnien | Fast computation of empirically tight bounds for the diameter of massive graphs[END_REF][START_REF] Roditty | Fast approximation algorithms for the diameter and radius of sparse graphs[END_REF][START_REF] Weimann | Approximating the diameter of planar graphs in near linear time[END_REF][START_REF] Yuster | Computing the diameter polynomially faster than APSP[END_REF].

Let n = |V | be the number of nodes and m = |E| be the number of edges. With n-1 graph searches (i.e. BFS traversals for unweighted graphs or Dijkstra searches for weighted graphs) of cost O(m) time each, where O(•) notation neglects poly-log factors, the above distances can be computed as a variant of the all-pairs shortest paths problem [START_REF] Dor | Allpairs almost shortest paths[END_REF][START_REF] Zwick | Exact and approximate distances in graphs -A survey[END_REF]. Many faster solutions have been proposed [START_REF] Noga Alon | On the exponent of the all pairs shortest path problem[END_REF][START_REF] Chan | More algorithms for all-pairs shortest paths in weighted graphs[END_REF][START_REF] Chan | All-pairs shortest paths for unweighted undirected graphs in o(mn) time[END_REF][START_REF] Michael | New bounds on the complexity of the shortest path problem[END_REF][START_REF] Galil | All pairs shortest paths for graphs with small integer length edges[END_REF][START_REF] Karger | Finding the hidden path: Time bounds for all-pairs shortest paths[END_REF][START_REF] Pettie | A new approach to all-pairs shortest paths on real-weighted graphs[END_REF][START_REF] Seidel | On the all-pairs-shortest-path problem in unweighted undirected graphs[END_REF][START_REF] Shoshan | All pairs shortest paths in undirected graphs with integer weights[END_REF][START_REF] Takaoka | An O(n 3 log log n/ log n) time algorithm for the all-pairs shortest path problem[END_REF][START_REF] Yuster | Computing the diameter polynomially faster than APSP[END_REF][START_REF] Zwick | All pairs shortest paths in weighted directed graphs-exact and almost exact algorithms[END_REF][START_REF] Zwick | All pairs shortest paths using bridging sets and rectangular matrix multiplication[END_REF], but no O(m 2-ε )-time algorithm is known for sparse graphs. On the other hand, a single graph search provides approximations with bounded error in O(m) time. Approximate solutions lying between these two extremes are interesting as they bring to light useful combinatorial properties [START_REF] Aingworth | Fast estimation of diameter and shortest paths (without matrix multiplication)[END_REF].

We consider algorithms for α-multiplicative βadditive approximations D, r and v that take O(m γ ) expected time. 1 Specifically, it is required that 1 α Dβ ≤ D ≤ D for the diameter, r ≤ r ≤ αr + β for the radius, and 1 α (v) -β ≤ v ≤ (v) for the eccentricities. Under these requirements we investigate the interplay among the parameters α, β and γ (the lower, the better), giving upper and lower bounds for the approximation quality using α, β and for the running time using γ. To motivate our work, we give an overview of the previous results in terms of α, β and γ, illustrating them for the diameter (Fig. 1a) and the eccentricities (Fig. 1c). Several other results exist but they address different aspects from what depicted here.

The upper bounds are reported as bullets in the upper envelopes of Figs. 1a,c. As discussed above, all the known exact algorithms achieve α = 1, β = 0 and γ = 2 (leftmost bullet). Also, a single graph search yields α = 2 for the diameter and the radius and α = 3 for the eccentricities, all with β = 0 and γ = 1 (rightmost bullet). Roditty and Vassilevska W. [START_REF] Roditty | Fast approximation algorithms for the diameter and radius of sparse graphs[END_REF] obtain α = 3/2, β < 1 and γ = 3/2 for D and r (middle bullet in Fig. 1a): they employ Las Vegas randomization to reduce the O(m √ n + n 2 ) time achieved in the seminal work by Aingworth, Chekuri, Indyk and Motwani [START_REF] Aingworth | Fast estimation of diameter and shortest paths (without matrix multiplication)[END_REF] to expected O(m √ n) time. Chechik, Larkin, Roditty, Schoenebeck, Tarjan and Vassilevska W. [START_REF] Chechik | Better approximation algorithms for the graph diameter[END_REF] present new deterministic algorithms, addressing also eccentricities, and obtain α = 3/2 for D, r and α = 5/3 for (v), all with β = 0 and γ = 3/2 (middle bullet in Fig. 1c).

Some conditional lower bounds are known, represented as shaded zones in Fig. 1, under the Strong Exponential Time Hypothesis (SETH) of Impagliazzo, Paturi and Zane [START_REF] Impagliazzo | Which problems have strongly exponential complexity?[END_REF] stating that for every ε > 0 there is an integer k such that k-SAT cannot be solved in time O(2 (1-ε)n ): any algorithm with α, β and γ below these bounds implies that SETH is false. Roditty and Vassilevska W. [START_REF] Roditty | Fast approximation algorithms for the diameter and radius of sparse graphs[END_REF] give a reduction from SAT to Algorithms in [START_REF] Chechik | Better approximation algorithms for the graph diameter[END_REF][START_REF] Roditty | Fast approximation algorithms for the diameter and radius of sparse graphs[END_REF] Single search the problem of distinguishing between diameter 2 and 3 in graphs implying that, under SETH, no algorithm can solve it in O(m 2-δ ) time: in particular, it is impossible to get α < 3/2, β = 0 and γ < 2. With their construction, the possibility of α < 3/2 with γ < 2 remains open if one allows for β ≥ 1. Chechik et al. [START_REF] Chechik | Better approximation algorithms for the graph diameter[END_REF] reduce SAT to the problem of distinguishing between graphs of diameter 3( + 1) and 4( + 1), where ≥ 0 is a given parameter, showing that it is impossible to get α < 4/3, β = O(m δ ), γ < 2 -2δ for any δ ≥ 0 under SETH. However, as noted by the authors, this construction still leaves open the possibility of 4/3 ≤ α < 3/2 with γ < 2 and β ≥ 1 (lighter shaded zone in Fig. 1a). Independently of this paper, Abboud, Vassilevska W. and Wang [START_REF] Abboud | Approximation and fixed parameter subquadratic algorithms for radius and diameter[END_REF] give a conditional lower bound for the eccentricities. They exclude α < 5/3 with β = 0 and γ < 2 (shaded zone in Fig. 1c) under the Orthogonal Vectors conjecture (OV), which is implied by SETH as shown by Williams [START_REF] Williams | A new algorithm for optimal constraint satisfaction and its implications[END_REF].

In this paper, we make three further steps in the study of the problem of approximating the extremal distances mentioned before. In particular, we obtain new bounds illustrated in Figs. 1b,d.

First, we describe a reduction from SAT to two problems on graphs: deciding whether the diameter is 3t or 2t, and deciding whether the maximum eccentricity over a given subset of nodes X ⊆ V is 5t or 3t. Under SETH, none of them can be solved when t > c • m δ in O(m 2-2δ-ζ ) time (for any c > 0, 0 ≤ δ < 1 and ζ > 0): hence it is impossible to get α < 3/2 for the diameter and α < 5/3 for the eccentricities with β = O(m δ ) and γ < 2 -2δ for any δ ≥ 0 under SETH. In this way we tighten the known bounds for the diameter and the eccentricities (shaded zones in Fig. 1b,d). In particular, the recently achieved approximation factors α = 3/2 for D and α = 5/3 for (v) cannot be improved in truly subquadratic time (γ < 2) even with an additive term β = O(1) under SETH. This also indicates that the eccentricities are more difficult to approximate than the diameter. Notice that our lower bound is incomparable with that in [START_REF] Abboud | Approximation and fixed parameter subquadratic algorithms for radius and diameter[END_REF], as the former holds with the more general condition β = O(m δ ) under SETH, while the latter holds under the weaker condition OV.

Second, we present an algorithmic scheme that gives nontrivial approximations with exponent γ = 1 + ε arbitrarily close to the minimum 1. Specifically, for any integer k ≥ 0, we present a randomized algorithm hinging on a novel iterative procedure that selects O(n 1/(k+1) ) nodes from which to launch the graph searches (for all pairs shortest paths, a different iterative sampling has been presented in [START_REF] Dor | Allpairs almost shortest paths[END_REF]). The properties of the selected nodes allow us to get α = 2 -1/2 k for diameter and radius and α = 3 -4/(2 k + 1) for eccentricities, with β < 1, in O(mn 1 k+1 ) expected time (thus γ = 1 + 1 k+1 ). For k ≥ 2, this gives a family of previously unknown bounds (crosses in Figs. 1b,d), and approaches near-linear time as k grows.

For example, when k = 2 we obtain α = 7/4 for diameter and radius and α = 11/5 for the eccentricities, in O(mn 1/3 ) expected time. Looking at Fig. 1, we can observe that previous work focused on bounds for α in [1, 3/2] (diameter and radius) and [1, 5/3] (eccentricities); instead, our results explore for the first time the ranges (3/2, 2] and (5/3, 3] (as we could not find any counterargument). Also, approaching γ ≈ 1 for larger values of α is crucial to analyze massive networks. Third, we study the size of distance h-dominating sets in undirected graphs of diameter D. An hdominating set X is a subset of the nodes at distance ≤ h from every other node in the graph. Our study is closely related to the possibility of fast diameter approximations, but could be of independent interest for other graph problems (e.g. facility location). We first show that an h-dominating set X can be used to produce an upper bound D of the diameter D in O(|X| • m) time, such that D ≤ D ≤ D + h. Upper bounds are crucial for approximations, as any approximation algorithm with bounded error must (implicitly or explicitly) provide one: in particular an α-multiplicative β-additive approximation D is equivalent to an upper bound D satisfying D ≤ D ≤ α(D + β), by choosing D = α( D + β).

A closer look at the algorithms in [START_REF] Aingworth | Fast estimation of diameter and shortest paths (without matrix multiplication)[END_REF][START_REF] Roditty | Fast approximation algorithms for the diameter and radius of sparse graphs[END_REF], when applied to undirected graphs, shows that they implicitly rely on the existence of an h-dominating set of size O( √ n) for h = (D + 1)/2. In our algorithmic scheme we explicitly find h-dominating sets of size O(n 1/(k+1) ) for h = 2 k -1 2 k (D + 1). To obtain faster approximation algorithms, one way is to find h-dominating sets X of smaller size: thus, it is interesting to study the size of X in the worst case, throwing a bridge between diameter approximation and extremal graph theory [START_REF] Bollobás | Extremal graph theory[END_REF][START_REF] Haynes | Fundamentals of Domination in Graphs[END_REF]. We analyze the upper bounds given by our algorithms and show several lower bounds through explicit constructions.

In particular, we consider the worst-case size of h-dominating sets for h = λ(D + δ), for some 0 ≤ λ < 1 and δ ≥ 0, because this is related to diameter approximations with α = λ+1 and β = λδ/α. If there is an h-dominating set X of size Θ(n ε ), then it is possible to use it to get γ = 1 + ε. Our results are illustrated in Fig. 2. First, we rule out the possibility to get ε < 1 for λ < 1/2 and δ = O(1). Second, we use a family of constructions G t to exclude ε < 1/ for λ < 1-

2 ( +1)+2
and δ ≤ 1, for any chosen ≥ 2. For some values of λ the bounds obtained by our algorithms are optimal (up to logarithmic factors). For these values, a faster algorithm for diameter approximation with α = λ + 1 would need new techniques to bound the diameter from above as it cannot rely on the existence of small h-dominating sets.

Finally, some interesting questions concern directed graphs. Previous work on diameter approximation does not distinguish between directed and undirected graphs, sharing the same algorithmic techniques. Here our results are tailored for undirected graphs, except for our lower bound on the diameter, which holds also for directed graphs. One of the reasons lies in a central lemma (Lemma 4.2) that does not hold for directed graphs as the inferred distances in the proof are not symmetrical (i.e. it can be d(x, y) = d(y, x)). We do not see this as a limitation of our results. Actually we leave open the possibility that the problem of approximating the diameter in undirected vs directed graphs could require different techniques and values of β, γ when 3/2 < α < 2 (Fig. 1b), while this situation does not seem to emerge for α = 3/2. It could be also interesting to investigate generalizations of h-dominating sets for directed graphs.

The paper is organized as follows. After some preliminaries in Section 2, we give the lower bound under SETH in Section 3. We present our approximation scheme in Section 4, and introduce our framework for distance dominating sets in Section 5.

We consider undirected graphs G = (V, E), with n = |V | nodes and m = |E| nodes (wlog m ≥ n). Each edge (u, v) ∈ E is associated with a real positive weight w(u, v) > 0, where conventionally w(u, v) = 1 for unweighted graphs. The maximum edge weight is denoted by M = max (u,v)∈E w(u, v), where M = 1 on unweighted graphs. We denote distances between any two nodes by d(u, v) and use the shorthand

d(S, v) = min u∈S d(u, v). The eccentricity of a node v ∈ V is (v) = max u∈V d(u, v). The diameter of G is D = D(G) = max v∈V (v) = max u,v∈V d(u, v
) and the radius is r = r(G) = min v∈V (v). We use the definitions of α-multiplicative β-additive approximations D, r and v given in Section 1, and simply say (almost) αapproximation when β = O(M ).

To work uniformly on weighted and unweighted graphs, we use the term graph search to indicate either a BFS traversal for unweighted graphs or a Dijkstra search for weighted graphs. We denote by C = C(n, m) the cost of this search: for example, C = O(m) for BFS and C = O(m + n log n) for Dijkstra implemented with Fibonacci heaps. We always assume C = O(m) and C = Ω(m). Given S ⊆ V , the value of d(S, v) for all the nodes v ∈ V can be computed in time O(C) by starting a graph search from a dummy node connected to every node in S: we call it multi-source graph search.

We define N (v) as the first nodes (v inclusive) discovered during a graph search launched from node v. In other words, N (v) contains the nearest nodes to v, breaking ties arbitrarily. We use the graphical notation u → v to denote an edge (u, v) traversed in a path, and u v to denote any shortest path from u to v (possibly empty if u = v).

Lemma 2.1. For any pair of nodes u, v ∈ V , we have

| (u) -(v)| ≤ d(u, v). Proof. Wlog (u) ≥ (v). Take x ∈ V so that (u) = d(u, x) ≤ d(u, v) + d(v, x) ≤ d(u, v) + (v). 2
We need the following known result on uniform random sampling, also used in [START_REF] Aingworth | Fast estimation of diameter and shortest paths (without matrix multiplication)[END_REF][START_REF] Roditty | Fast approximation algorithms for the diameter and radius of sparse graphs[END_REF].

Lemma 2.2. Given a family H of at most n sets each of size over a universe U of size L, a random sampling of Θ(L/ •log n) elements hits all the sets in H with high probability.

Proof. For any H ∈ H the probability that an element u ∈ U sampled uniformly at random is not in H is L- L . If S ⊆ U contains s elements sampled independently and uniformly at random, then

P[S ∩ H = ∅] = P[u / ∈ H] s = ( L- L ) s
. By the union bound, the probability p that S ∩ H = ∅ for some H ∈ H is at most:

|H| • P[S ∩ H = 0] = n • L- L s = n • 1 -L L s• /L = O(n • e -s• /L ). If s = α • L/ • log n for some constant α, then p = O(n • e -α•log n ) = 1/n Ω(α) . 2
3 Hardness of improved approximations

We transform an instance ϕ of k-SAT into an undirected, unweighted graph G ϕ t (of exponential size) of diameter 2t or 3t, where the latter occurs iff ϕ is satisfiable. Our transformation is based on the construction of Roditty and Vassilevska W. [START_REF] Roditty | Fast approximation algorithms for the diameter and radius of sparse graphs[END_REF] which produces graphs of diameter 2 and 3. Chechik et al. [START_REF] Chechik | Better approximation algorithms for the graph diameter[END_REF] showed a related construction that gives diameter 3t or 4t respectively, for any t ≥ 1. Still, it is challenging to obtain 3t and 2t. We need the gadget graph T t [B] described below.

For a given node set B and t ≥ 1, the gadget respectively. We say that a partial assignment p ∈ P i satisfies a clause γ ∈ C if γ contains at least one literal evaluating to true under p. We extend the set of clauses

T t [B] is a graph T = (V, E) on node set V = B ∪ Q, where Q is a
u ∈ B u ∈ Q u (z-1) c . . . . . . . . . . . . . . . u ∈ B u ∈ Q u (z-1) u (z)
C to C * = C ∪ {δ 1 , δ 2 }
, where δ i is a dummy clause satisfied by the partial assignments p ∈ P i only. 2 Then, we build the set P * = P 1 ∪P 2 ∪{π}, where π is an empty partial assignment that does not satisfy any clause. The graph G ϕ t = (V, E) is defined as follows. We start with a node set U containing a node u γ for every clause γ ∈ C * . Then, for each partial assignment p ∈ P * we introduce a new node w p and define the gadget

T p = (V p , E p ) = T t [{w p } ∪ U p ],
where U p = {u γ ∈ U : γ is not satisfied by p}. The graph G ϕ t is the union of the gadgets T p : specifically, V = p∈P * V p and E = p∈P * E p , with U ⊆ V as V π ⊃ U π = U and V p ∩ V q ⊆ U for p = q as private nodes of different gadgets are distinct. d) edges by Proposition 3.1 and can be constructed trivially knowing U p . Thus, the total time and size is at most t • 2 d/2+o (d) . 2

Proposition 3.2. G ϕ t contains t • 2 d/2+o(d) edges and can be constructed in t • 2 d/2+o(d) time. Proof. Observe that |P * | = 2 • 2 d/2 + 1 = 2 d/2+o(d) and |C * | = O((2d) k ) = 2 O(k•log d) = 2 o(d) as we do not have duplicated clauses and k is constant. Computing U p for every p ∈ P * requires O(|P * | • |C * | • k) = 2 d/2+o(d) time. Each of the |P * | gadgets has O(t • |C * | + |C * | 2 ) = t • 2 o(
Proposition 3.3. Any path in G ϕ t that does not contain a node in U between its endpoints is also a path in T p for some p ∈ P * and in particular both its endpoints belong to V p . Proof. Otherwise, take two consecutive edges x → v → y along the path which belong to distinct gadgets T p and T q . They must be incident to a node v ∈ V p ∩ V q ⊆ U .2 Proof. We first show that ϕ is satisfiable iff there exist two disjoint sets U p and U q for some p, q ∈ P * . Observe that the sets U p and U q are disjoint iff every clause in C * = C ∪ {δ 1 , δ 2 } is satisfied by either p or q. The dummy clauses δ 1 and δ 2 are both satisfied iff p and q belong respectively to P 1 and P 2 , and thus form a valid total assignment p∪q. Moreover, p∪q satisfies ϕ iff each clauses in C is satisfied by either p or q (as the clauses are disjunctive). As any total assignment satisfying ϕ can be written as p∪q for p ∈ P 1 ⊆ P * and q ∈ P 2 ⊆ P * , the claim is proven.

The following four facts hold.

(i) We have d(w p , w q ) ≥ 2t for any p = q.

Take any shortest path from w p to w q . By Proposition 3.3 it contains a node v ∈ U , since w p and w q belong to distinct gadgets. Thus d(w p , w q ) = d(w p , v) + d(v, w q ) ≥ 2t by Proposition 3.4.

(ii) If d(a, b) > 2t for some nodes a and b, then some sets U p and U q are disjoint.

Take p, q ∈ P * such that a ∈ V p and b ∈ V q . If U p and U q are not disjoint there is a node

z ∈ U p ∩ U q ⊆ V p ∩ V q . As a, z ∈ V p and z, b ∈ V q we get d(a, b) ≤ d(a, z) + d(z, b) ≤ 2t by Proposition 3.1.
(iii) If U p and U q are disjoint, then d(w p , w q ) ≥ 3t.

Notice that p = q as U p and U q are non-empty (they contain u δ1 or u δ2 ). Any shortest path from w p to w q contains a node v ∈ U by point (i) above. If there is no other v ∈ U on the path, then w p , v ∈ V p and v, w q ∈ V q by Proposition 3.3, and in particular v ∈ V p ∩ V q ∩ U ⊆ U p ∩ U q contradicting our assumption. So, the path is of the form

w p v v w q with distinct v, v ∈ U . Hence d(w p , w q ) = d(w p , v) + d(v, v ) + d(v , w q ) ≥ 3t by Proposition 3.4.
(iv) For any two nodes a and b, we have d(a, b) ≤ 3t. Take p, q ∈ P * such that a ∈ V p and b ∈ V q . Consider a path a u δ(p) u δ(q) b where δ(s) is the clause δ i not satisfied by s. Since a, u δ(p) ∈ V p , u δ(p) , u δ(q) ∈ V π and u δ(q) , b ∈ V q , we have d(a, b) ≤ 3t by Proposition 3.1.

The four facts above imply that the diameter is either 2t or 3t, and the latter occurs iff ϕ is satisfiable.

2

For even t = 2z, all the gadgets T p appearing in G ϕ Proof. Suppose by contradiction to have a procedure A distinguishing between diameter-3t and diameter-2t

graphs for t > c • m δ in O(m 2-2δ-ζ ) = O(m (1-δ)(2-ε) ) time for some ζ, ε > 0, c > 0 and 0 ≤ δ < 1. Fix γ = ε/4: under SETH there is a k such that k-SAT cannot be solved in O(2 (1-γ)d ) time.
Consider an instance ϕ of k-SAT in d-variables. By Proposition 3.2, for some µ = 2 d/2+o(d) the graph G ϕ t contains m ≤ µt edges and can be constructed in O(µt) time. As δ < 1, we can pick t = Θ(µ

δ 1-δ ) such that t > c • µ δ t δ ≥ c • m δ and m ≤ µt = O(µ 1+ δ 1-δ ) = O(µ 1
1-δ ). Notice that for any input graph with m = µt edges, the procedure A runs in O(m (1-δ)(2-ε) ) = O(µ 2-ε ) time but takes Ω(µt) time to read the graph, hence we can assume µ 2-ε = Ω(µt). To solve ϕ, we construct the graph G ϕ t , which by Lemma 3.1 has diameter 2t or 3t according to the satisfiability of ϕ, then we apply the procedure A to distinguish the two cases (as we picked t > c • m δ ). The procedure A runs in Proof. We adapt the proof of Theorem 3.1. Notice that we used our hypothetical procedure distinguishing diameter-3t and diameter-2t graphs only on instances of the form G ϕ t . On such instances having t = 2z, this is equivalent to telling whether = max p∈P * { (c p )} is 5z or 3z by Lemma 3.2. Thus, any procedure performing the latter in O(m 2-2δ-ζ ) time yields to the same contradiction. Corollary 3.2. Under SETH, there is no algorithm giving a ( 5 3 -ε)-multiplicative O(m δ )-additive approximation of all the eccentricities in a graph in O(m 2-2δ-ζ ) time, for any ε > 0, 0 ≤ δ < 1 and ζ > 0. In particular, there is no almost

O(m (1-δ)(2-ε) ) = O(µ 2-ε ) time where µ 2-ε = Ω(µt) dominates the O(µt) cost of constructing the graph. Thus, the total time is O(µ 2-ε ) = 2 (2-ε)•d/2+o(d) = 2 (1-ε 2 )d+o(d) = 2 (1-2γ)d+o(d) = O(2 (1-γ)d ) contradicting SETH. 2
( 5 3 -ε)-approximation in O(m 2-ζ ) time.
Proof. Following the proof of Corollary 3.1, we take a small enough 4 γ > 0 such that the eccentricity estimation v satisfies v ≥ 3 5 (v) + γ (v) -c • m δ . For c = c/(5γ) and z > c • m δ = c • m δ /5γ, our procedure can decide whether the maximum eccentricity over a given subset of nodes X is 3z or 5z. In the first case v ≤ (v) ≤ 3z for any v ∈ X. In the second case, for some v ∈ X we have (v) = 5z and

v ≥ 3z + γ • 5z -c • m δ > 3z.

Fast approximation algorithms

We begin with a motivating example: we are given in input an undirected unweighted graph of diameter 8 and we want to output a pair of nodes at distance 5 or more from each other. By performing a BFS from an arbitrary node in the graph, we are guaranteed to find another node at distance at least 4 from it, but this is not sufficient. On the other hand, by running a 3/2-approximation algorithm for the diameter, we are guaranteed to find two nodes at distance 6 from each other in O(m √ n) time. We show that it is possible to obtain distance 5 in O(mn 1/3 ) time, with high probability.

(1) Suppose that every node has ≥ n 2/3 nodes at distance ≤ 3. (Call " -neighborhood" of a node the set of nodes at distance ≤ from it.) In this case, a random sampling of Θ(n 1/3 ) nodes hits the 3-neighborhood of every node with high probability by Lemma 2.2: in particular one of the sampled nodes is at distance ≤ 3 from a diametral node and by Lemma 2.1 it has eccentricity ≥ 8 -3 = 5. We run a BFS from each of the sampled nodes (they are only O(n 1/3 )) so we are guaranteed to find a pair of nodes at distance ≥ 5 from each other. 4 For approximation factor 5 3 -ε, choose γ = (2) Suppose that there is a node z of degree < n 1/3 . We launch a BFS from z, hence we can assume that (z) ≤ 4 as otherwise the BFS finds two nodes at distance ≥ 5 from each other. We also run a BFS from each of the neighbors of z (they are less than n 1/3 ), which together are at distance ≤ 3 from the rest of the graph, since (z) ≤ 4. In particular, there is a neighbor of z at distance ≤ 3 from a diametral node, and by Lemma 2.1 it has eccentricity ≥ 8 -3 = 5. As we run a BFS from all the neighbors of z, we are guaranteed to find two nodes at distance ≥ 5 from each other.

(3) We are left with the hard case: there is a node w which has few (< n 2/3 ) nodes at distance ≤ 3 and every node has many (degree ≥ n 1/3 ) neighbors at distance 1. Even if the node w is not known, it can be found easily by sampling Θ(n 1/3 ) nodes at random and then picking the node farthest from the sampled set, as noted by Roditty and Vassilewska W. [START_REF] Roditty | Fast approximation algorithms for the diameter and radius of sparse graphs[END_REF]. We run a BFS from w so we can assume (w) ≤ 4. Then, we exploit the fact that w has few nodes at distance ≤ 3 and that every node has many neighbors at distance 1 in order to find a small set at distance ≤ 3 from all the nodes in the graph. Once obtained this set, we can run a BFS from each of its elements and find a node of eccentricity ≥ 8-3 = 5.

In order to obtain this set we proceed as follows. Consider the nodes in the 2-neighborhood of w and observe that their respective neighbors are all within distance 3 from w. Thus, the 1neighborhoods of every node in the 2-neighborhood of w form a family of sets, each of size ≥ n 1/3 , over a universe of size < n 2/3 (the 3-neighborhood of w). By sampling O(n 1/3 ) nodes uniformly at random from the 3-neighborhood of w, we hit all the sets in the family with high probability by Lemma 2.2. That is, with high probability the set of sampled nodes is at distance ≤ 1 from every node in the 2neighborhood of w. Notice that the 2-neighborhood of w is in turn at distance ≤ 2 from the rest of the graph, as (w) ≤ 4. Hence, with high probability the sampled nodes are at distance ≤ 2 + 1 = 3 from every node the graph.

The ideas employed in cases 1 and 2 have been already used in the literature. The approach behind some previous diameter approximation algorithms is to look for a node w such that the set W = N (w) for some small > 0 contains nodes at large distance h from w (this roughly corresponds to case 2). In general, this set may not exist in a graph for a given distance h: this happens if every node v has more than nodes at distance h. Still, in this case there is a useful hitting set S of size O(n/ ) at distance h from every node v (this roughly corresponds to case 1). In the algorithms by Aingworth et al. [START_REF] Aingworth | Fast estimation of diameter and shortest paths (without matrix multiplication)[END_REF] and by Roditty and Vassilevska W. [START_REF] Roditty | Fast approximation algorithms for the diameter and radius of sparse graphs[END_REF] these ideas are applied to give sets W and S of size O( ) = O(n/ ) = O( √ n). Our algorithm introduces a novel machinery (based on the idea given in case 3) that proceeds iteratively to obtain smaller and smaller sets W i = N i (w i ).

Sampling procedure

Our approximation algorithms begin with a sampling procedure that outputs a sequence of nodes w 1 , . . . , w k ∈ V and node sets S 0 , . . . , S k ⊆ V , which have the property to be sufficiently close to all the nodes in the graph (in a way that will be formalized in Lemma 4.3).

We perform k iterations, numbered from 0 to k -1, where k is a constant parameter. In the first iteration i = 0, we proceed similarly to case 1. We build S 0 by sampling Θ(q • log n) nodes uniformly at random, where q = Θ(n 1 k+1 ). By Lemma 2.2, we have that S 0 hits with high probability the sets N 1 (u) for every node u, where 1 = n/q . We also pick the node w 1 farthest from S 0 . Letting h 0 = d(S 0 , w 1 ) and W 1 = N 1 (w 1 ), we have with high probability that W 1 contains a node in S 0 (which is at distance ≥ h 0 from w 1 ), so W 1 contains all the nodes at distance < h 0 from w 1 .

Since W 1 is not small enough (it has size 1 = O(n/q)), we do not use it directly. Instead we pass it along to the next iteration i = 1. At each iteration i = 1, . . . , k -1, we are given the set W i = N i (w i ) containing the nodes at distance < h i-1 from w i , and we look for a smaller set W i+1 = N i+1 (w i+1 ) containing the nodes at distance < h i from w i+1 . To achieve this, we proceed as in case 3. We build a set S i by sampling Θ(q • log n) nodes uniformly at random from the universe W i of size i . By Lemma 2.2, we have that S i hits with high probability the sets N i+1 (u), where i+1 = i /q , but this time only for those nodes u such that N i+1 (u) ⊆ W i .

We pick the node w i+1 farthest from Z i = (V \W i )∪ S i , so that w i+1 is far from S i but its close neighbors do not fall outside W i . More precisely, letting h i = d(Z i , w i+1 ), we will prove that W i+1 = N i+1 (w i+1 ) contains all the nodes at distance < h i from w i+1 (see fact c in the proof of Lemma 4.2), under the condition W i+1 ∩Z i = ∅. This condition holds with high probability (see Lemma 4.1), yielding a Monte Carlo algorithm. To obtain a Las Vegas one, we check the condition at the end of iteration i: if it does not hold, we repeat the iteration i resampling S i . The crucial part of our analysis is to generalize the idea given in case 3, to show that if h i-1 is large but h i is small, then S i is close to every node in the graph (see Lemma 4.2).

Finally, after iteration k -1, we are left with a set W k = N k (w k ) of size k = O(n/q k ). Similarly to case 2, we keep the whole set W k for the approximation.

For uniformity, we define W 0 = V , 0 = n, and Z 0 = (V \ W 0 ) ∪ S 0 = S 0 so we do not need to treat the first iteration in a special way. Similarly, we define

S k = W k and Z k = (V \ W k ) ∪ S k = V . By choosing q = (n/ log n) 1 k+1 , we minimize |S 0 ∪• • •∪S k | to O(n 1 k+1 ), as shown in Proposition 4.2.
The whole procedure is summarized in Algorithm 1.

Lemma 4.1. In Algorithm 1, the condition W i+1 ∩Z i = ∅ in step 2d holds with high probability.

Proof. Consider the family of sets H = N i+1 (u) : u ∈ V and N i+1 (u) ⊆ W i on the universe W i . We apply Lemma 2.2 to show that S i hits every set in H with high probability. Indeed, we have |H| ≤ n, |W i | = i , each set in the family N i+1 (u) has size i+1 , and S i contains Θ (q

• log n) = Θ ( i / i+1 • log n) nodes sampled uniformly at random from W i . If W i+1 ⊆ W i then W i+1 ∩ Z i ⊇ W i+1 ∩ (V \ W i ) = W i+1 \ W i = ∅. Otherwise, W i+1 = N i+1 (w i+1 ) ∈ H. Hence, with high probability S i hits W i+1 and W i+1 ∩ Z i ⊇ W i+1 ∩ S i = ∅. 2
∪ • • • ∪ S k | = O(n 1 k+1 log k k+1 n). Proof. Each set S 0 , . . . , S k-1 is of size Θ(q • log n) = O((n/ log n) 1 k+1 •log n) = O(n 1 k+1 log k k+1 n) by construc- tion. Notice that i = O(n/q i ), thus |S k | = |W k | = k = O(n/q k ) = O(n/(n/ log n) k k+1 ) = O(n 1 k+1 log k k+1 n). 2
For any 0 ≤ i ≤ k, let h i be the maximum distance from Z i to any node in the graph, where h k = 0 by construction as Z k = V . The set W i+1 contains all the nodes at distance < h i from w i+1 . (See fact c in the next proof.) We relate the distances d(S i , v) with the values h i . For i = 0, we have Z 0 = (V \ W 0 ) ∪ S 0 = S 0 as W 0 = V , thus d(S 0 , v) ≤ h 0 . For i ≥ 1, we obtain the following.

Algorithm 1 Sampling procedure.

Input: Undirected graph G = (V, E) and a constant integer parameter k ≥ 0.

Output: Nodes w 1 , . . . , w k ∈ V and node sets S 0 , . . . , S k ⊆ V .

1. Let W 0 = V , 0 = n and q = (n/ log n) 1 k+1 .

2. For each i = 0, 1, . . . , k -1:

(a) Sample Θ(q • log n) nodes uniformly at random from W i .

Let S i be the set of sampled nodes.

(b) Run a multi-source graph search from Z i = (V \ W i ) ∪ S i . Let w i+1 be the last visited node.

(c) Perform a graph search from w i+1 . Let W i+1 be the set containing the first i+1 = i /q visited nodes.

(d) Check that W i+1 ∩ Z i = ∅. If the check fails, repeat iteration i.

3. Set S k = W k . (Also, define Z k = (V \ W k ) ∪ S k = V for uniformity.) Lemma 4.2. For 1 ≤ i ≤ k and any node v ∈ V , we have either d(S i , v) ≤ h i or d(S i , v) ≤ d(w i , v) -h i-1 + 2h i + M .
Proof. We will use the following facts.

(a) For any node

u ∈ V either d(S i , u) ≤ h i or d(V \ W i , u) ≤ h i , as h i is the maximum distance from Z i = (V \ W i ) ∪ S i to any node. (b) If u ∈ W i then d(u, w i ) ≤ d(V \ W i , w i ), as W i comprises the i nearest nodes to w i . (c) We have d(V \ W i , w i ) ≥ h i-1 . Take a node z ∈ W i ∩ Z i-1 (as it exists due to the condition in step 2d). By (b), d(V \ W i , w i ) ≥ d(z, w i ) ≥ d(Z i-1 , w i ) = h i-1 as w i is the farthest node from Z i-1 .
Fix a node v ∈ V . Consider a shortest path P from w i to v. Let a be the last node on P such that

d(S i , a) ≤ h i . The node a exists since d(S i , w i ) ≤ h i . Indeed, taking any node u ∈ S i ⊆ W i , we have d(S i , w i ) ≤ d(u, w i ) ≤ d(V \ W i , w i ) by (b): this implies that d(S i , w i ) ≤ h i by (a).
If a = v, then d(S i , v) ≤ h i and the statement is proven. Otherwise, take the node b which follows a on P , so the path P is of the form

w i a → b v with d(S i , b) > h i . By (a), d(V \ W i , b) ≤ h i . As d(V \ W i , w i ) ≥ h i-1 by (c), then d(w i , b) ≥ h i-1 -h i by triangle inequality. 5 Writing P as w i b v we get d(b, v) = d(w i , v) -d(w i , b) ≤ d(w i , v) -(h i-1 -h i ). We can bound d(S i , v) as d(S i , v) ≤ d(S i , a) + w(a, b) + d(b, v) ≤ h i + M + d(w i , v) -(h i-1 -h i ) = d(w i , v) - h i-1 + 2h i + M . 2 Lemma 4.3. Let v ∈ V be any node. For some 0 ≤ ı ≤ k, we have d(S ı , v) ≤ h ı ≤ (2 k-ı -1)(∆ + M ), where ∆ = max 1≤i≤k {d(w i , v) -d(S i , v)}.
Proof. As h 0 is the maximum distance from Z 0 = S 0 , we have d(S 0 , v) ≤ h 0 . Let ı ∈ {0, . . . , k} be the maximum index ı such that d(S ı , v) ≤ h ı . We show h i ≤ (2 k-i -1)(∆ + M ) for ı ≤ i ≤ k, proving the lemma. Start with i = k: we have (2 k-i -1)(∆+M ) = 0 and h k = 0 by construction. Now suppose inductively h i ≤ (2 k-i -1)(∆+M ) for some ı < i ≤ k. We need to show h i-1 ≤ (2 k-(i-1) -1)(∆ + M ). By the assumption i > ı, it cannot be d(S i , v) ≤ h i (as ı is the maximum index satisfying this condition), so it must be that

d(S i , v) ≤ d(w i , v) -h i-1 + 2h i + M by Lemma 4.2. Therefore h i-1 ≤ 2h i + d(w i , v) -d(S i , v) + M ≤ 2h i + ∆ + M ≤ 2 • (2 k-i -1)(∆ + M ) + ∆ + M = (2 k-(i-1) -1)(∆ + M ). 2

Approximations

We obtain the approximations by exploiting our sampling procedure as shown in Algorithm 2. Notice that we obtain (w i ) during the sampling as we run a graph search from w i .

2 k+1 -1 M (diame- ter), 2 k -1 2 k M (radius) and 2 k -1 3•2 k -1 M (eccentricities).
Corollary 4.1. For arbitrarily small ε > 0, there is δ > 0 such that in O(mn ε ) expected time it is possible to give an almost (2 -δ)-approximation of the diameter and the radius and an almost (3 -δ)-approximation of all the eccentricities of an undirected graph with additive error < M .

Distance dominating sets

We recall the definition of (distance) h-dominating sets [START_REF] Haynes | Fundamentals of Domination in Graphs[END_REF][START_REF] Henning | Total domination in graphs[END_REF].

Definition 1. In a graph G = (V, E), a subset of the nodes X ⊆ V is a (distance) h-dominating set if d(X, u) ≤ h for every node u ∈ V .
We start by showing that Algorithm 1 relies on hdominating sets.

S i , v) ≥ d(X, v). Thus, d(X, v) ≤ (2 k -1)(D -d(X, v) + M ), hence d(X, v) ≤ 2 k -1 2 k (D + M ). The bound |X| = O(n 1 k+1 log k k+1 n) is given by Proposition 4.2.
2

This observation implicitly leads to the following purely combinatorial result. ), for any constant k ≥ 0. This is shown in Fig. 2, for λ = 2 k -1

2 k and ε = 1 k+1 . We now show our general approach to obtain an estimation of the diameter from an h-dominating set. First, we produce an upper bound D as described next. Proof. Compute the value h 0 = max u∈V d(X, u) with a multi-source graph search, taking O(C) time. As X is a h-dominating set, we have h 0 ≤ h. 6 Then, compute

D 0 = max x∈X (x) ≤ D in O(|X| • C) time running a graph search from each x ∈ X. Return the value D = D 0 + h 0 ≤ D + h. To prove that D ≤ D, take v ∈ V and x ∈ X such that (v) = D and d(x, v) = d(X, v) ≤ h 0 . We obtain D = (v) ≤ (x) + d(x, v) ≤ D 0 + h 0 = D. 2

Lower bounds on h-dominating sets

We presented a general algorithmic approach to approximate the diameter by finding small-size h-dominating sets. To better understand the properties of this approach and its limitations, it is natural to provide lower bounds on the size of these sets in the worst case and in relation to the diameter D.

The specific case h = 1 and D = 2 has been already studied in the literature since a distance 1-dominating set is a classical dominating set. Desormeaux et al. [START_REF] Desormeaux | Total domination in graphs with diameter 2[END_REF] prove that in undirected graphs of diameter 2 the smallest 1-dominating set has size Θ( √ n log n) in the worst case. 7 We provide several lower bounds, with focus on the coefficients λ and δ that relate h and D as h = λ(D + δ). Our bounds are illustrated as shaded zones in Fig. 2.

We first obtain a lower bound from the gadget graph T t [B] defined in Section 3. We now provide a family of constructions for every integer ≥ 2. Each construction for a fixed value of produces a family of graphs G t parameterized by an integer t ≥ . The graph G t contains n = t nodes and has diameter D = ( +1)

2

. Moreover, we prove that every h-dominating set for h < D is of size Ω(t) = Ω(n 1/ ).

Construction G 2 t

For simplicity, we first describe the construction in the special case = 2. We then generalize the construction for other values of and rigorously prove our claims.

The node set of G 2 t contains the pairs of natural numbers xy ∈ {1, . . . , t} 2 . For any node ab ∈ {1, . . . , t} 2 , there is a "write" edge ab Any path starting from a node ab ∈ {1, . . . , t} 2 matches the following pattern

εε → δε → δε|εδ → δδ → • • •
where ε ::= a|b and δ ::= 1| . . . |t. Hence, the nodes at distance 2 (or less) from any node ab match the pattern δε|εδ, thus their number is O(t). This implies that any 2-dominating set of G 2 t needs Ω(t) = Ω( √ n) nodes to reach all the n = t 2 nodes in the graph.

A family of constructions G t

We now fully describe our family of constructions (thus a family of families of graphs). For a given ≥ 2, we define the graphs G t parametrized by t ≥ . The node set of G t contains the sequences of coordinates over the natural numbers x 1 . . . x ∈ {1, . . . , t} . For a node a 1 • • • a and any x ∈ {1, . . . , t}, we have a "write" edge that writes the first coordinate:

a 1 a 2 • • • a W -→ xa 2 • • • a .
Then, for i ∈ {1, . . . , -1}, we have an edge which swaps the coordinates i and i + 1, thus for a node a 1 • • • a we have

a 1 • • • a i a i+1 • • • a Si -→ a 1 • • • a i+1 a i • • • a .
The resulting graph is clearly undirected. Proof. Let a 1 • • • a and x 1 • • • x be any two nodes. For every j ∈ {1, . . . , } there is a path

x -j+2 • • • x a j • • • a Sj-1 -→ Sj-2 -→ • • • S1 -→ a j x -j+2 • • • x a j+1 • • • a W -→ x -j+1 • • • x a j+1 • • • a
of length j. Concatenating these paths we get

a 1 • • • a -→ x 1 a 2 . . . a -→ • • • -→ x -j+2 • • • x a j • • • a -→ • • • -→ x 1 • • • x , which is a path from a 1 • • • a to x 1 • • • x of length j=1 j = ( +1) 2 . 2
Lemma 5.2. In the graph G t , the nodes at distance ≤ p from any given node are O(t q ), where q is the largest integer such that q(q+1) 2 ≤ p.

Proof. Let a = a 1 . . . a be a given node. Consider any node x = x 1 . . . x and define b i = 0 if x i ∈ {a 1 , . . . , a } and b i = 1 otherwise. We define the size of x as s(x) = i=1 b i . We give a weight i to the i-th coordinate, and define the potential of x as p(x) = i=1 i • b i . The following facts hold. 2. We have s(x) ≤ q, where q is the largest integer such that q(q+1) 2 ≤ p(x). Fixed a maximum potential p, the largest size q is obtained by the greedy choice b 1 , . . . , b q = 1 and b q+1 , . . . , b = 0, where the potential is q j=1 j = q(q+1) 2 ≤ p.

Thus, the nodes at distance at most p from a given node a have size at most q, and their number is at most q s=0 s • (t -) s • -s = O(t q ). Indeed, the value s varies over the possible values of s(x); the term l s comes from the choice of which b i are set to 1; the terms (t -) s and -s come from the choice of the values for the coordinates x i where b i = 1 and b i = 0, respectively. 2 Theorem 5.3. For every ≥ 2 and infinite values of n, there exists a family of undirected unweighted graphs of diameter D = ( +1) 2 and number of nodes n where any h-dominating set for h < D has size Ω(n 1/ ).

Proof. Consider the graphs G t for t → ∞. First, the number of nodes is n = t by construction. Second, the diameter is at most ( +1) 2 by Lemma 5.1. Third, by Lemma 5.2 there are at most O(t -1 ) nodes at distance strictly less than ( +1) 2 from any given node. For large enough t, this number is less than the total number of nodes t : hence there are some nodes in the graph at distance at least ( +1) 2 from any given node, and in particular the diameter is exactly D = ( +1) 2 .

Since the nodes at distance h < D from any given node are only O(t -1 ), we need at least Ω(t) different nodes to reach at distance h all the t nodes in the graph. Hence, any h-dominating set for h < D has size Ω(t) = Ω(n 1/ ). 2

Corollary 5.2. For ≥ 2, λ < 1 - Hence, the family G t is such that every h-dominating set has size Ω(t) = Ω(n 1/ ). 2

Figure 1 :

 1 Figure 1: α-multiplicative O(1)-additive approximations in O(m γ ) expected time.

1 Figure 2 :

 12 Figure 2: h-dominating sets of size O(n ε ) for h = λ(D + δ).

2 3. 1

 21 set of additional private nodes. The purpose of this graph is to make the nodes in B at distance exactly t from each other. For t = 1, T 1 [B] is the complete graph on B, with no private node. For t = 2, we introduce a private node c ∈ Q and define T 2 [B] as the star with center in c and tips in B. To construct T t+2 [B], we first introduce a distinct private node u ∈ Q for every u ∈ B. Then, we build the gadget T t [B ] = (B ∪ Q , E ) on the node set B = {u : u ∈ B} and add an edge (u , u) for every u ∈ B. Specifically, we defineQ = B ∪ Q and E = E ∪ {(u , u) : u ∈ B}.The result is a star-like structure, illustrated in Fig.3where private nodes are colored black. Proposition 3.1. T t [B] contains O(t • |B|) nodes and O(t • |B| + |B| 2 ) edges. For any a, b ∈ V we have d(a, b) ≤ t with equality iff a, b ∈ B and a = b. In T 2z [B], for any a ∈ V we have d(c, a) ≤ z with equality iff u ∈ B. The only shortest path between u, v ∈ B contains c. Proof. The statements are trivially true for T 1 [B] and T 2 [B]. In the general case, they can be shown by induction noticing that any shortest path in T t+2 [B] is a shortest path in T t [B ] possibly concatenated with an edge (u, u ) at each endpoint u, if u ∈ B. Construction of G ϕ t Let ϕ be an instance of k-SAT on an even number d of variables D = {x 1 , . . . , x d } and c clauses C = {γ 1 , . . . , γ c }. We first preprocess ϕ to remove duplicated clauses, so we assume the γ i 's are distinct. Then, we divide the variables in two sets D 1 and D 2 , each of size d/2, and construct the sets P 1 and P 2 , containing the 2 d/2 partial assignments on the variables in D 1 and D 2 ,

Figure 3 :

 3 Figure 3: Gadget T t [B] for |B| = 5 and t = 2z (left) or t = 2z + 1 (right).

Proposition 3 . 4 .

 34 For any two distinct non-private nodes a, b ∈ U ∪ {w p : p ∈ P * }, we have d(a, b) ≥ t. Proof. Take a shortest path a b and apply Proposition 3.3. If it is a path on T p , then d(a, b) = t by Proposition 3.1. Otherwise, it is of the form a v b with v ∈ U distinct from a and b, hence d(a, b) = d(a, v) + d(v, b) ≥ 2t by induction. 2 Lemma 3.1. G ϕ t has diameter either 2t or 3t. It is 3t iff ϕ is satisfiable.

2zLemma 3 . 2 . 2 Theorem 3 . 1 .

 32231 have a center, say c p ∈ V p . In G ϕ 2z the maximum eccentricity = max p∈P * (c p ) among the centers c p of all the gadgets T p is either 3z or 5z. It is 5z iff ϕ is satisfiable.Proof. By Lemma 3.1 it is sufficient to prove = D -z.We first prove (c p ) ≤ D -z for any p ∈ P * . For nodes v ∈ V p , we haved(c p , v) ≤ z ≤ D -z by Proposition 3.1. If v / ∈ V p ,any shortest path from w p to v has to pass through c p . Indeed, consider the first node u ∈ U on the shortest path, which must exist by Proposition 3.3: the sub-path w p u contains c p by Proposition 3.1. Write the path as w p c p v: we have d(c p , v) = d(w p , v) -d(w p , c p ) ≤ D -z as d(w p , v) ≤ D and d(w p , c p ) = z by Proposition 3.1. Now we show (c p ) ≥ D -z for some p ∈ P * . Take a diametral node v so that (v) = D and p ∈ P * such that v ∈ V p : we have d(c p , v) ≤ z by Proposition 3.1 and (c p ) ≥ (v) -d(c p , v) ≥ D -z by Lemma 2.1. Under SETH, there is no algorithm distinguishing between diameter-3t and diameter-2t graphs when t > c • m δ in O(m 2-2δ-ζ ) time, for any c > 0, 0 ≤ δ < 1 and ζ > 0.

Corollary 3 . 1 . 2 Theorem 3 . 2 .

 31232 Under SETH, there is no algorithm giving a ( 3 2 -ε)-multiplicative O(m δ )-additive approximation of the diameter in O(m 2-2δ-ζ ) time, for any ε, ζ > 0 and 0 ≤ δ < 1. In particular, there is no almost ( 3 2 -ε)-approximation in O(m 2-ζ ) time. Proof. Consider a procedure that gives a ( 3 2 -ε)multiplicative c • m δ -additive approximation D of the diameter D. Take a small enough 3 γ > 0 such that D satisfies D ≥ 2 3 D + γD -c • m δ . For c = c/(3γ) and t > c • m δ = c • m δ /(3γ), our procedure distinguishes diameter-2t and diameter-3t graphs: in the first case D ≤ D = 2t while in the second case D ≥ 2t + γ • 3tc • m δ > 2t. Hence, by Theorem 3.1 it cannot run in O(m 2-2δ-ζ ) time for any ζ > 0. Under SETH, there is no algorithm deciding whether the maximum eccentricity over a given subset of nodes X is 5z or 3z when z > c • m δ in O(m 2-2δ-ζ ) time, for any c > 0, 0 ≤ δ < 1 and ζ > 0.

2 3

 2 For approximation factor 3 2 -ε, choose γ = 4ε 3(3-2ε) .

2 Remark 1 .

 21 By Theorem 3.2, any procedure that performs this cannot run in O(m 2-2δ-ζ ) time for any ζ > 0. Under SETH, Theorem 3.1 excludes the possibility of a truly sub-quadratic algorithm that takes a graph of constant diameter D = 3t and produces an approximation D >2 3 D = 2t. This result is surprisingly tight: when D is constant but not divisible by 3, an O(m 2-δ )-time algorithm that produces a value D >2 3 D is possible, as shown by Roditty and Vassilevska W.[START_REF] Roditty | Fast approximation algorithms for the diameter and radius of sparse graphs[END_REF].

9ε 5 ( 5 -

 55 3ε) .

Proposition 4 . 3 . 1 k+1)

 431 Algorithm 2 takes O(n 1 k+1 log k k+1 n • C) = O(mn 1 k+1 ) expected time. Proof. Step 1 runs in O(k • C) expected time by Proposition 4.1. Step 2 performs |S 0 ∪ • • • ∪ S k | graph searches Theorem 4.1. For any k ≥ 0, Algorithm 2 gives an almost (2 -1 2 k )-approximation of the diameter and the radius and an almost (3-4 2 k +1 )-approximation of all the eccentricities of an undirected graph in O(n expected time, where C is the cost of a graph search. The additive terms are 2 k -1

Proposition 5 . 1 .

 51 The set X = S 0 ∪ • • • ∪ S k generated by Algorithm 1 is a 2 k -1 2 k (D + M )-dominating set of size |X| = Let v ∈ V be any node. By Lemma 4.3, we have d(X, v) ≤ d(S ı , v) ≤ (2 k-ı -1)(∆ + M ) where ∆ ≤ D -d(X, v), as d(w i , v) ≤ D and d(

Theorem 5 . 1 .

 51 Every undirected graph of n nodes admits a 2 k -1 2 k (D + M )-dominating set of size O(n 1 k+1

Proposition 5 . 2 .

 52 Given a h-dominating set X ⊆ V , it is possible to produce an upper bound D of the diameterD such that D ≤ D ≤ D + h in O(|X| • C) time.

=

  If h = λ(D + δ) for some known constants λ and δ, then the upper bound D obtained with Proposition 5.2 can be transformed into a (λ+1)-multiplicative λδ λ+1 -additive approximation D. It is sufficient to choose as estimation of the diameter the value D = D-λδ λ+1 . Indeed, we have D = D-λδ λ+1 ≤ D+h-λδ λ+1 D+λ(D+δ)-λδ λ+1 = D and D ≥ D-λδ λ+1 = 1 λ+1 D -λδ λ+1 as required by the definition of α-multiplicative β-additive approximation. In particular, applying Proposition 5.2 to the 2 k -1 2 k (D + M )dominating set X produced by Algorithm 1 in O(C) expected time (by Proposition 5.1), we obtain an alternative proof of our bounds for diameter approximation.

Theorem 5 . 2 . 2 Corollary 5 . 1 .

 52251 For any integer constant D ≥ 1 and infinite values of n, there exists a family of undirected unweighted graphs of diameter D and number of nodes n where any h-dominating set for h < D/2 has size Θ(n). Proof. Consider the gadget graph T t [B] on a set B of size s → ∞. The number of nodes in is n = Θ(s) and the diameter is D = t by Proposition 3.1. Consider any h-dominating set X for h < D/2: it must contain at least one node per branch, in order to be at distance ≤ h from each tip u ∈ B. Hence, |X| ≥ s = Θ(n). For any constants λ < 1/2 and δ = O(1), and infinite values of n, there exists a family of undirected unweighted graphs of diameter D and number of nodes n where any h-dominating set for h = λ(D +δ) has size Θ(n). Proof. For λ < 1/2 and δ = O(1), we can pick a large enough D such that h = λ(D + δ) < D/2. 2

W-→W

  xb for any x ∈ {1, . . . , t}, and a "swap" edge ab S -→ ba. Note that for any edge xy → x y there is an edge x y → xy, hence the graph is undirected. The diameter is at most 3 as for any two nodes ab and xy there is a path ab

Lemma 5 . 1 .

 51 The diameter of G t is at most ( +1) 2 .

1 .

 1 We have p(x) ≤ d(a, x). By induction, p(a) = 0 and x → y implies p(y) ≤ p(x) + 1. Indeed, if x W -→ y, then only b 1 can change and it has weight 1. If x Si -→ y instead, then the values of b i and b i+1 are swapped (and the others do not change) and their weights differ by one unit only.

2 ( 2 (

 22 +1)+2 , and infinite values of n, there exists a family of undirected unweighted graphs of some diameter D and number of nodes n where any h-dominating set for h = λ(D + 1) has size Ω(n 1/ ).Proof. Observe that λ < 1and h = λD + λ < D D+1 D + D D+1 = D.

  Proposition 4.2. Algorithm 1 returns sets S 0 , . . . , S k with |S 0

	Proof. Steps 1 and 3 take at most linear time. In each
	iteration in step 2, the time spent in substeps 2a and 2d
	is dominated by the O(C) cost of substeps 2b and 2c. As
	the condition in substep 2d holds with high probability
	by Lemma 4.1, each iteration is repeated a constant
	number of times in expectation. As we perform k
	iterations for constant k, the total cost is O(C) expected
	time.	2

Proposition 4.1. Algorithm 1 runs in O(C) expected time, where C is the cost of a graph search.

For example δ i = x ∨ x, where x is any variable in the group D i .

Here and in (b)-(c) we are implicitly using the hypothesis that the graph is undirected.

In fact, here we discover that X is an h 0 -dominating set, but in general it can be h 0 < h.

Desormeaux et al. [13] consider total dominating sets. On graphs without isolated nodes, a dominating set of size t can be transformed into a total dominating set of size 2t[START_REF] Henning | Total domination in graphs[END_REF], hence their Ω( √ n log n) lower bound still holds.

Algorithm 2 Approximation of the diameter, the radius and all the eccentricities.

Input: Undirected graph G = (V, E) and an integer k ≥ 0.

Output: Approximations D (diameter), r (radius) and v (eccentricity of every node v ∈ V ).

1. Execute Algorithm 1 and obtain w 1 , . . . , w k ∈ V and S 0 , . . . , S k ⊆ V .

2. Run a graph search from every node x ∈ S 0 , . . . , S k .

Return:

and by Proposition 4.2 runs in O(n

Finally, step 3 does not increase the asymptotical time complexity as the values D, r and v can be be computed during the previous steps at no extra cost. 2

Lemma 4.4. Algorithm 2 returns D such that

Proof. Note that D = (u) ≤ D for some u ∈ V . Take v such that (v) = D. For any i, we have

Apply Lemma 4.3 to v, where ∆ ≤ 2r -r and

Remark 2. A single graph search gives a 3approximation of all the eccentricities in the graph. Suppose we start the search from x ∈ V : it is suffi-

Proof. Consider any node v and notice that the value v is obtained either as d(u, v) or as (u) -d(u, v) for some node u ∈ V . As (u) ≤ (v) + d(u, v) by Lemma 2.1, in either case we get v ≤ (v).

For every i, we have

Apply Lemma 4.3 to the node v, where ∆ ≤

. We get

2 + M ). This inequality already gives us a lower bound on v . However, we obtain a better bound treating the case ı = 0 separately.

When ı = 0, we have h ı = h 0 ≤ (2 k -1)(∆ + M ). Take a node u such that (v) = d(v, u). As h 0 is the maximum distance from Z 0 = S 0 , we have d(S 0 , u) ≤ h 0 . Now take