A Fine-Grained Dichotomy for the Center Problem on Gromov Hyperbolic Graphs

In order to sketch our strategy to prove Theorem 1, we need to introduce a few more notations and terminology. For every two vertices $u$ and $v$, let the (metric) interval $I(u,v)$ be defined as the set of all vertices $w$ on a shortest $uv$-path (i.e., such that $d(u,v)=d(u,w)+d(w,v)$). For every $k$ such that $0\le k\le d(u,v)$, let $S_k(u,v)=\{w\in I(u,v):d(u,w)=k\}$ be called a slice. Our basic strategy would be to compute a pair $u,v$ of mutually distant vertices (i.e., such that $e(u)=e(v)=d(u,v)$), using a few BFS, then to extract a central vertex from a middle slice. This approach has been used in the design of linear-time algorithms for the Center problem on various graph classes [19, 36, 51]. A refinement of it was presented in [18] for chordal graphs: such that either we extract a central vertex from a middle slice or we compute a new pair $u^{\prime },v^{\prime }$ of mutually distant vertices such that $d(u^{\prime },v^{\prime })>d(u,v)$. Since for chordal graphs $d(u,v)\ge diam(G)-2$, a central vertex is found after a constant number of iterations. Our algorithm follows a similar strategy to these prior works, although we must tackle with new challenges that are specific to $\frac{1}{2}$-hyperbolic graphs. More specifically, in some cases where $d(u,v)=2r-1$ is odd, previous techniques can neither be used to extract a central vertex from the middle slices $S_{r-1}(u,v)$ and $S_r(u,v)$, nor to find a new pair $u^{\prime },v^{\prime }$ of distance larger than $d(u,v)$. In this situation, we extend the search for a central vertex to the neighborhoods of both slices. The latter requires inspecting the vertices at a distance of up to $3$ from the slices in order to guide the search. Hence, as a side contribution of this work, we bring new insights on the structure of the balls centered at a clique of a $\frac{1}{2}$-hyperbolic graph.

Another difference between [18] and our Theorem 1 is the implementation of the distance-to-clique procedure. Roughly, the procedure must output some distance information for every vertex of a clique, which includes their respective eccentricities. The linear-time implementation proposed in [18, Sec. 3] was based on a property of chordal graphs that does not hold for $\frac{1}{2}$-hyperbolic graphs (namely, that cliques in a chordal graph are outergated, see Sec. 2). We propose a different implementation, which is based on recent results about cliques in a graph with convex balls (a superclass of chordal graphs and $\frac{1}{2}$-hyperbolic graphs) [16].

Recall that the algorithm presented in this paper is proved to be correct under the unchecked assumption that the input graph is $\frac{1}{2}$-hyperbolic. If we run this algorithm on an arbitrary input, then it may fail, or it may output a non-central vertex. The latter raises the question of deciding whether a graph is $\frac{1}{2}$-hyperbolic. The problem was studied in [25], where a subcubic equivalence was proved between the recognition of $\frac{1}{2}$-hyperbolic graphs and the detection of an induced $C_4$. Combined with the results from [53], it implies that we can decide whether a graph is $\frac{1}{2}$-hyperbolic in $O(n^{\omega +o(1)})$ time, where denotes the square matrix multiplication exponent. We complete these prior works with the following conditional lower bound (the definition of the Strong Exponential-Time Hypothesis is recalled in Sec. 4):

A similar hardness result was proved in [10], but only for the recognition of $1$-hyperbolic graphs. The $1$-hyperbolic graphs are much less structured than the $\frac{1}{2}$-hyperbolic graphs. For example, every graph with diameter at most three is $1$-hyperbolic [49].

Finally, we complete Theorem 1 with the following hardness result on the Center problem for $1$-hyperbolic graphs:

The missing proofs in what follows can be found in the full version of the paper [35].

There are other so-called “negative curvature” parameters on graphs, that can only differ from Gromov hyperbolicity by a small multiplicative factor; see [15]. One of these parameters, the slimness, has received special attention [30]. Although the differences between these parameters and Gromov hyperbolicity are irrelevant in the design of approximation algorithms, they may lead to varying behaviors, for small values, when considering exact algorithms. For instance, we can prove that linear-time center computation can only be achieved for graphs with slimness $0$ (a.k.a., the block graphs), whereas it essentially requires quadratic-time, under the Hitting Set conjecture, for any positive value of slimness. The latter result is a byproduct of our proof for Theorem 3.

By symmetry (up to reverting the respective roles of $u$ and $v$), it suffices to prove the result for the slice $S_{\lfloor \frac{d(u,v)}{2}\rfloor }(u,v)$. Let $z\in V$ be arbitrary. It suffices to prove that $d(w,z)\le \lceil \frac{d(u,v)}{2}\rceil +1$ for every $w\in S_{\lfloor \frac{d(u,v)}{2}\rfloor }(u,v)$. For that, since $u$ and $v$ are mutually distant, $d(u,z)\le d(u,v)$ and $d(v,z)\le d(u,v)$. In particular, the balls $B_{\lfloor \frac{d(u,v)}{2}\rfloor }(u),B_{\lceil \frac{d(u,v)}{2}\rceil }(v)\text{and}{B}_{\lceil \frac{d(u,v)}{2}\rceil }(z)$ pairwise intersect. Let $\mathscr{H}(G)$ be the injective hull of $G$. Since $\mathscr{H}(G)$ is a Helly graph, there is a vertex $c_z$ of $\mathscr{H}(G)$ such that $d(c_z,u)=\lfloor \frac{d(u,v)}{2}\rfloor$, $d(c_z,v)=\lceil \frac{d(u,v)}{2}\rceil$, and $d(c_z,z)\le \lceil \frac{d(u,v)}{2}\rceil$. By Lemma 5, $\mathscr{H}(G)$ is $\frac{1}{2}$-hyperbolic. Therefore, by Lemma 4.1, $d(w,c_z)\le 1$ for every $w\in S_{\lfloor \frac{d(u,v)}{2}\rfloor }(u,v)$. It implies $d(z,w)\le d(z,c_z)+d(c_z,w)\le \lceil \frac{d(u,v)}{2}\rceil +1$. $◀$

Lemma 10 can be directly used in order to solve the even case of our algorithm (case of mutually distant vertices at an even distance).

For the odd case, our first intent was to reuse the strategy from [18]: either we extract a central vertex from a middle slice, or we find a new pair of mutually distant vertices at a larger distance. For that, the following procedure can be used:

However, the strategy sketched above can only be used in order to solve the odd case $d(u,v)=2r-1$ if the middle slice $S_{r-1}(u,v)$ has eccentricity $r$. The example of Fig. 1 shows that it is not always the case.

Suppose by contradiction $S_2(w,x)$ and $S_2(w^{\prime },x)$ are uncomparable for inclusion, for some $w,w^{\prime }\in p{r}_x(K)$. Let $y\in S_2(w,x)\setminus S_2(w^{\prime },x)$ and let $y^{\prime }\in S_2(w^{\prime },x)\setminus S_2(w,x)$. By Lemma 4.1, both $S_2(w,x)$ and $S_2(w^{\prime },x)$ are cliques. Since $K$ is $2$-outergated (Lemma 8.1), $S_2(w,x)\cap S_2(w^{\prime },x)\ne \mathrm{\varnothing }$. Therefore, $d(y,y^{\prime })\le 2$. However, by the ${\alpha }_1$-metric property, $d(y,y^{\prime })\ge d(y,w)+d(w^{\prime },y^{\prime })=4$. A contradiction. $◀$

We combine Lemma 16 with Lemma 6.2, to prove the following important result:

We next summarize ways to restrict the search for a central vertex, using outergates and some convexity arguments:

We need one more technical lemma:

The proof of Proposition 15 now follows from the analysis of Algorithm 1. See also Fig. 2 for an illustration. The implementation of the algorithm can be reduced to $O(1)$ calls to BFS (either from a start vertex, or from a start subset), and to the procedure of Lemma 9. Therefore, the running time is linear.

Let us sketch the correctness proof of this algorithm. First, we force the clique $K$ to satisfy the following Property $(\alpha )$: $\forall z\in V\setminus F(K),\forall w\in K,d(z,w)\le r$. The intuition goes as follows: assume that we can find a vertex $v_L\in N(K)$ such that $F(K)\subseteq B_r(v_L)$. Then, either $e(v_L)\le r$, or $e(v_L)=r+1$ and $F(v_L)\subseteq V\setminus F(K)$. Furthermore, in the latter situation, assuming Property $(\alpha )$ we can consider any edge between $v_L$ and $K$; by applying the ${\alpha }_1$-metric property to this edge, we can prove that every vertex of $F(v_L)$ has eccentricity $\ge 2r$ (lines 65–69). In order to enforce Property $(\alpha )$, we use the set of vertices $F^{\prime }(K)=\{z\in V:d(z,K)=r\}$ (lines 2–11). If $F^{\prime }(K)=\mathrm{\varnothing }$, then Property $(\alpha )$ already holds. Otherwise, either some vertex of $K$ is at distance at most $r$ to every vertex of $F^{\prime }(K)$, in which case we can restrict $K$ to $K^{\prime }=\{w\in K:{\psi }_K(w,F^{\prime }(K))=F^{\prime }(K)\}$ (see Lemma 18.2); or we can output a vertex of eccentricity $\ge 2r$ (Lemma 12).

For every $x\in F(K)$, let $g_K(x)$ be an outergate of $x$ in $B_2(K)$, whose existence follows from Lemma 17. Let $M=\{g_K(x):x\in F(K)\}$. Roughly, most of the algorithm (lines 12–59) is devoted to the search for a vertex $v_L$ such that $M\subseteq B_2(v_L)$. Such a vertex, if any, may not be central, but it satisfies $F(K)\subseteq B_r(v_L)$. For that, we fix an arbitrary $x_0\in F(K)$. Let $M_0^{\prime }$ be the subset of vertices in $M$ that are at distance at most $2$ to $p{r}_{x_0}(B_2(K))$. We start searching in $p{r}_{x_0}(B_2(K))$ for a vertex $s_0$ such that $M_0^{\prime }\subseteq B_2(s_0)$ (lines 28–34). Let $L$ be the subset of all such vertices $s_0$. Then, using an arbitrary $z_L$ such that $d(z,L)>r$, we go closer to $K$ by searching for a $c_L\in N(K)\cap N(L)$ such that $c_L\in B_r(z_L)$, and $M_0^{\prime }\subseteq B_2(c_L)$ (see Lemma 18.1). Doing so, let $w_L\in N(c_L)\cap K$ be arbitrary, and let $W_L=S_1(w_L,x_0)$. We claim that $d(g_K(x),W_L)\le 2$ for every $x\in F(K)$. Indeed, this is true if $g_K(x)\in M_0^{\prime }$, because $c_L\in W_L$. Otherwise ($g_K(x)\notin M_0^{\prime }$), we apply Lemma 19 to $g_K(x),g_K(x_0)\text{and}{w}_L$. We end up searching for $v_L$ in $W_L$, which by Lemma 4.1 is a clique.

The sub-procedure for searching $v_L$ may fail if $diam(M)\ge 4$. More specifically, sometimes we cannot compute an intermediate vertex with the desired properties, in which case we rather find some $x,x^{\prime }\in F(K)$ such that $d(g_K(x),g_K(x^{\prime }))\ge 4$. Nevertheless, whenever it happens, by Lemma 18.1 there are only two possibilities: either $d(g_K(x),g_K(x^{\prime }))>4$, and there is no $c\in N(K)$ such that $e(c)\le r$; or $d(g_K(x),g_K(x^{\prime }))=4$, and so we can restrict the search for such a vertex $c$ to $S_2(g_K(x),g_K(x^{\prime }))$. In these situations, we replace $x_0$ with one of $x$ or $x^{\prime }$, then we apply the sub-procedure of lines 15–26. Finally, in a few more technical situations, the search for a vertex $v_L$ may fail even if $diam(M)\le 3$. However, when it happens, we can either directly output a vertex $a$ such that $e(a)\le r$ ($a$ may not be in $N(K)$, see lines 37 & 42), or $e(a)\ge 2r$ (using Lemma 12, see lines 44 & 54); or we can assert that there is no $c\in N(K)$ such that $e(c)\le r$. Furthermore, in the latter situation, we return an arbitrary vertex of $K$ (lines 16, 24 & 50).

Let $u,v$ be mutually distant vertices. If $d(u,v)=2r$ (even case), by Corollary 11, every vertex of minimum eccentricity within $S_r(u,v)$ is central. Hence, we shall assume for the remainder of the proof $d(u,v)=2r-1$ (odd case). By Lemma 10, we are left deciding whether $rad(G)=r$ or $rad(G)=r+1$, and returning a central vertex. If $r=1$, then both $u$ and $v$ are universal. In particular, both $u$ and $v$ are central, and so we can return any of those vertices. From now on, we shall assume $r\ge 2$. By Lemma 14, a vertex of eccentricity at most $r$, if any, must be contained either in $B_1\left(S_{r-1}(u,v)\right)$, or in $B_1\left(S_r(u,v)\right)$. We first consider $K=S_{r-1}(u,v)$, which by Lemma 4.1 is a clique. There are two cases:

If $e(K)=r$, then we follow the same strategy as in [18]. More specifically, let $c\in K$ be maximizing ${\psi }_K(c)$. If $e(c)=r$, then $c$ is central. Otherwise, let $u^{\prime }\in F(c)$. By Corollary 13, $e(u^{\prime })\ge 2r$. Furthermore, by Lemma 4.2, $e(u)=e(v)=2r-1\ge diam(G)-1$. Therefore, $e(u^{\prime })=diam(G)=2r$. Let $v^{\prime }\in F(u^{\prime })$ be arbitrary. We replace $u,v$ with the diametral pair $u^{\prime },v^{\prime }$. By doing so, we are back to the even case.

Otherwise, by Lemma 10, $e(K)=r+1$; furthermore, also by Lemma 10, $e(w)=r+1$ for every $w\in K$. Let $a$ be the vertex returned by the process-clique procedure of Proposition 15 (Algorithm 1). If $e(a)=r$, then $a$ is central. Else, if $e(a)\ge 2r$, then we conclude as before $e(a)=2r=diam(G)$. We replace $u$ and $v$ with $a$ and an arbitrary vertex of $F(a)$. By doing so, we are back to the even case. Otherwise, $e(a)=r+1$, and by Proposition 15, there is no vertex of eccentricity $r$ within $B_1(K)$. In the latter sub-case, we next consider $K=S_r(u,v)$. We proceed exactly as before, with the exception of the last sub-case: when $e(K)=r+1$, and the vertex $a$ returned by the process-clique procedure has eccentricity $r+1$. Then, by Proposition 15 (applied twice), there is no vertex of eccentricity $r$ within $B_1\left(S_{r-1}(u,v)\right)\cup B_1\left(S_r(u,v)\right)$. By Lemma 14, $rad(G)=r+1$, and $a$ is central.

We apply Lemma 4.3 to compute a pair $u,v$ of mutually distant vertices. Then, we run two BFSs: from $u$ and $v$, respectively. In the even case, since by Lemma 4.1 $S_r(u,v)$ is a clique, a vertex of minimum eccentricity within the slice can be computed by applying the procedure of Lemma 9.3. We now focus on the odd case, and we further assume $r\ge 2$ (the sub-case $r=1$ is trivial). Since we apply the same procedure to $S_{r-1}(u,v)$ and $S_r(u,v)$, it suffices to detail the implementation of this procedure for a fixed clique $K$. We run a BFS with start subset $K$ to compute $e(K)$ and $F(K)$. If $e(K)=r$, then we compute the vertex $c$ by applying Lemma 9.1; then, we compute $e(c)$ and $F(c)$ by running a BFS from $c$. If $e(K)=r+1$, then we apply Proposition 15; the eccentricity of its output $a$ can be computed from a final BFS. The overall running-time is therefore in $O(n+m)$. $◀$