Going Beyond Surfaces in Diameter Approximation

An area that is technique-wise related is the design of approximate distance oracles. After a preprocessing step, we would like to quickly estimate any $(u,v)$-distance within factor $(1+\epsilon )$. Thorup [53] exploited the fact that planar graphs admit balanced separators consisting of two shortest paths to give an oracle with preprocessing time $𝒪({(1/\epsilon )}^2\cdot n{\log }^{3}n)$, space $𝒪((1/\epsilon )\cdot n\log n)$, and query time $𝒪(1/\epsilon )$. The shortest path separators constitute a crucial ingredient of all the three aforementioned algorithms for estimating planar diameter as well.

Abraham and Gavoille [3] presented a generalization of shortest path separators to graph classes excluding a minor and extended Thorup’s oracle to such classes. However, their separators no longer enjoy such a nice structure. The main caveat is that already in a single balanced separator one might need to use paths $P_1,P_2$ such that $P_2$ is a shortest path only in $G-P_1$. Hence $P_2$ may be much longer than $\mathrm{𝖽𝗂𝖺𝗆}(G)$, which is easily seen to be unavoidable already in the class of apex graphs²²2$G$ is called an apex graph if $G$ can be made planar by removal of a single vertex., and it is unclear how to exploit such a separator for diameter computation. The second issue is that finding the separator requires highly superlinear time, which burdens the preprocessing time of the oracle. Almost-linear preprocessing time is currently available only for graphs of bounded genus [40] and for unit disk graphs [13]. The lack of well-structured balanced separators beyond surface-embeddable graphs seems to have limited the development of efficient metric-related algorithms so far.

There are two directions of generalizing the topological graph classes. First, one can pick $𝒪(1)$ faces in the surface embedding of a graph and replace them with certain graphs of pathwidth $𝒪(1)$, which are called the vortices. Second, one can insert a set of $𝒪(1)$ vertices, called the apices, and connect them possibly to anyone. The structural theorem of Robertson and Seymour [48] states that for any graph $H$, all the graphs excluding $H$ as a minor can be constructed from graphs embeddable in some fixed surface using these two operations and by taking a clique-sum of them.

When the excluded minor $H$ is an apex graph, this description can be slightly restricted [25]. What is important to us, apex-minor-free graphs enjoy the local treewidth property: their treewidth is bounded in terms of the (unweighted) diameter and this relation is known to be linear [24]. Note that the diameter of an edge-weighted graph cannot be related to treewidth by any means because the diameter can be reduced by scaling the weights, while the topological structure of the graph remains the same. Nevertheless, we will see that the local treewidth property is still useful in the considered setting.

The main message of this work is that the local treewidth property can be used instead of shortest path separators for the sake of approximating diameter and radius, as well as for efficient construction of distance oracles. We first employ it to tackle apex-minor-free graphs but we also show that its usefulness is not limited to such graph classes.

Suppose we have a list of vertices $S=(s_0,s_1,\mathrm{\dots },s_{k-1})$ in $G$ and we want to (approximately) learn all the distance patterns, between a vertex $v$ and all of $S$. Chan and Skrepetos [12] employed Cabellos’s technique of abstract Voronoi diagrams [10] to build a data structure to browse such distance patterns in the case when $G$ is planar and $S$ lie on a single face. However, this technique relies heavily on the embedding of the graph.

A more versatile argument was given by Li and Parter [47] in order to approximate planar diameter in a distributed regime. Following their convention, a subset $U^{\prime }\subseteq U$ is called a $\delta$-additive core-set of $U$ if for every $u\in U$ there exists $u^{\prime }\in U^{\prime }$ such that for each $i\in [0,k)$ we have $|d(u,s_i)-d(u^{\prime },s_i)|\le \delta$. When $\delta =\epsilon \cdot \mathrm{𝖽𝗂𝖺𝗆}(G)$, a trivial rounding argument yields a $\delta$-additive core-set of size ${(1/\epsilon )}^k$. Remarkably, the dependence on $k$ can be in fact removed from the exponent [47]. This theorem relies on a bound on the VC dimension of a certain set system and this argument carries over to any minor-free graph class [46]. A direct consequence of these theorems reads as follows. (Here $K_h$ stands for the $h$-vertex clique.)

For the sake of completeness, we provide a proof in Section 2. The local treewidth property will allow us to apply this lemma for $k=\mathrm{𝗉𝗈𝗅𝗒}(1/\epsilon )$ to efficiently compress information about distances in large subgraphs.

A set system is a collection $ℱ$ of subsets of some set $U$. We say that a subset $Y\subseteq A$ is shattered by $ℱ$ if $\{Y\cap S:S\in ℱ\}=2^Y$ , that is, every subset of $Y$ is an intersection of $Y$ with some $S\in ℱ$. The VC dimension of a set system is the size of the largest shattered subset. The notion of VC dimension was introduced by Vapnik and Chervonenkis [54]. What is important to us, a set system of bounded VC dimension cannot be too large.

First, in time $𝒪(k^7\cdot n\log n)$ one can compute a tree decomposition $(T,\chi )$ of $G$ of width $k^{\prime }=𝒪(k^2)$ [31]. By a standard argument, we can modify $(T,\chi )$ to have size $𝒪(n)$. Next, we turn $(T,\chi )$ into a binary rooted tree decomposition of depth $𝒪(\log n)$ and width at most $4k^{\prime }+3$ in time $𝒪(n)$ [20]. This also preserves the bound $|V(T)|=𝒪(n)$. $◀$

Orient the path $P$ from $u$ to $v$ and define $u^{\prime },v^{\prime }$ as the first and the last vertices from $C$ appearing on $P$. Since $u^{\prime },v^{\prime }$ lie on a shortest $(u,v)$-path, we have $d_G(u,u^{\prime })+d_G(v^{\prime },v)\le d_G(u,v)$. Next, it holds that each of $d_G(w,u^{\prime })$, $d_G(w,v^{\prime })$ is at most $\delta$. Hence $d_G(u,w)\le d_G(u,u^{\prime })+\delta$ and $d_G(w,v)\le d_G(v^{\prime },v)+\delta$, which yields the desired inequality. $◀$

We will now show how, using a tree decomposition of the cluster graph of width $𝒪({(1/\epsilon )}^2)$, to construct a distance oracle and estimate eccentricities. We give a unified proof for both statements because the constructed oracle is directly applied to obtain the second result. The presented algorithm is arguably simpler than the recursive schemes based on shortest path separators since in the analysis we only need to manage $𝒪(1)$ rounding errors, rather than $𝒪(\log n)$. We no longer need to assume that the excluded minor is an apex graph and this will allow us later to apply Theorem 17 in a more general setting.

Let us clarify that the parameter $\tau$ does not have to be given and it only appears in the analysis. However, we can always assume that the diameter is known within factor 2 after computing any eccentricity.

We begin with some notation that will be used throughout the proof. We will use variables $u,v$ to denote vertices of $G$ and variables $i,j$ to index the set of clusters. For a cluster $i\in 𝒞$, let $\mathrm{𝗅𝗈𝖼}(i)$ denote the node $t\in V(T)$ that is closest to the root among those satisfying $i\in \chi (t)$. We naturally extend this notation to vertices of $G$: all vertices $v\in C_i$ receive $\mathrm{𝗅𝗈𝖼}(v)=\mathrm{𝗅𝗈𝖼}(i)$. This mapping can be computed for all clusters and vertices in linear time by scanning $T$ top-down.

For $t\in V(T)$ let $U_t\subseteq 𝒞$ denote the set of clusters $i\in 𝒞$ for which $\mathrm{𝗅𝗈𝖼}(i)$ lies in the subtree of $T$ rooted at $t$, inclusively. Next, let $V_t={\bigcup }_{i\in U_t}{C}_i$.

For each $i\in 𝒞$ the nodes $t$ satisfying $i\in U_t$ must be lie on the $\mathrm{𝗅𝗈𝖼}(i)$-to-root path in $T$ and so there are $𝒪(\log n)$ of them. Hence each $i\in 𝒞$ contributes $𝒪(|C_i|\cdot \log n)$ to the sum ${\sum }_{t\in V(T)}|V_t|$, which yields the upper bound as $𝒞$ is a partition of $|V(G)|$. This argument leads directly to an algorithm computing the sets $V_t$. $\mathrm{⊲}$

Consider $t\in V(T)$, $i\in 𝒞$, and $v\in V(G)$. We call $(t,i,v)$ a valid triple when $t=\mathrm{𝗅𝗈𝖼}(i)$ and $v\in V_t$. For fixed $t\in V(T)$, the number of valid triples in which $t$ appears is at most $(w+1)\cdot |V_t|$, and so by Claim 18 the number of valid triples is $𝒪(w\cdot n\log n)$.

Recall that for $i\in 𝒞$ the vertex $c_i\in C_i$ is the center of cluster $i$. We will populate table $\mathrm{𝗂𝗇𝗇𝖾𝗋}\text{-}\mathrm{𝖽𝗂𝗌𝗍}$ indexed by valid triples, so that $\mathrm{𝗂𝗇𝗇𝖾𝗋}\text{-}\mathrm{𝖽𝗂𝗌𝗍}[t,i,v]$ will store the exact $(v,c_i)$-distance within the graph $G[V_t]$. If there is no such path, we set $\mathrm{𝗂𝗇𝗇𝖾𝗋}\text{-}\mathrm{𝖽𝗂𝗌𝗍}[t,i,v]=\mathrm{\infty }$.

Consider $t\in V(T)$. For each $i\in 𝒞$ with $\log (i)=t$, we compute all distances from $c_i$ in $G[V_t]$ using the linear single-source shortest path algorithm for $K_h$-minor-free graphs [52]. The total running time, over all $t\in V(T)$, is proportional to the number of valid triples. $\mathrm{⊲}$

We now argue that information gathered in table $\mathrm{𝗂𝗇𝗇𝖾𝗋}\text{-}\mathrm{𝖽𝗂𝗌𝗍}$ is sufficient to retrieve all distances in $G$, up to small additive error. This is the only place where we rely on the fact that each cluster has small strong diameter.

Let $Q$ be a shortest $(u,v)$-path in $G$. Next, let ${𝒞}_Q\subseteq 𝒞$ denote the set of clusters intersected by $Q$ and let $T_Q\subseteq V(T)$ be the set of nodes in which ${𝒞}_Q$ appear, i.e., $T_Q={\chi }^{-1}({𝒞}_Q)$. Since $G_{𝒞}$ is a contraction of $G$, the subgraph $G_{𝒞}[{𝒞}_Q]$ is connected. Consequently, $T_Q$ induces a connected subtree of $T$. Let $t\in T_Q$ be the node that is closest to the root among $T_Q$. Note that $t=\mathrm{𝗅𝗈𝖼}(i)$ for some $i\in {𝒞}_Q$.

We claim that the pair $(t,i)$ satisfies the requested conditions. Note that for each $j\in {𝒞}_Q$ the node $\mathrm{𝗅𝗈𝖼}(j)$ lies in the subtree of $T$ rooted at $t$. Hence ${𝒞}_Q\subseteq U_t$ and so $V(Q)\subseteq V_t$. In particular, we obtain that $u,v\in V_t$ so $(t,i,u)$, $(t,i,v)$ are valid triples (Item 1).

Since $Q$ is a shortest $(u,v)$-path and $V(Q)\subseteq V_t$, we infer that the $(u,v)$-distance in $G[V_t]$ equals their distance in $G$. Now we apply Lemma 16 to the graph $H=G[V_t]$ and $C=C_i,w=c_i$. Because $i\in {𝒞}_Q$, we know that $Q$ intersects $C_i$. It is crucial that all $C_i$-vertices are within distance $\delta$ from $c_i$ when considering distances within $G[C_i]$ (Definition 13(2)), not just in $G$. As $C_i\subseteq V_t$, this property carries over to the graph $H$. Lemma 16 implies that $d_H(u,c_i)+d_H(c_i,v)\le d_H(u,v)+2\delta$. We have $\mathrm{𝗂𝗇𝗇𝖾𝗋}\text{-}\mathrm{𝖽𝗂𝗌𝗍}(t,i,u)=d_H(u,c_i)$, $\mathrm{𝗂𝗇𝗇𝖾𝗋}\text{-}\mathrm{𝖽𝗂𝗌𝗍}(t,i,v)=d_H(c_i,v)$, and $d_H(u,v)=d_G(u,v)$, which yields Item 2. $\mathrm{⊲}$

We iterate over all pairs $t\in V(T),i\in 𝒞$ for which $(t,i,u)$ and $(t,i,v)$ are valid triples. There are only $𝒪(\log n)$ candidates for $t$ just because $(t,i,u)$ is a valid triple and so $t$ must lie on the $\mathrm{𝗅𝗈𝖼}(u)$-to-root path. For each such $t$ there are clearly at most $w+1$ candidates for $i$.

We return $x$ equal to the minimum value of $\mathrm{𝗂𝗇𝗇𝖾𝗋}\text{-}\mathrm{𝖽𝗂𝗌𝗍}[t,i,u]+\mathrm{𝗂𝗇𝗇𝖾𝗋}\text{-}\mathrm{𝖽𝗂𝗌𝗍}[t,i,v]$ taken over all such pairs $(t,i)$. For each $(t,i)$ the considered sum is either $\mathrm{\infty }$ or it equals the length of some $(u,v)$-walk in $G[V_t]$. This implies that $x\ge d_G(u,v)$. The inequality $x\le d_G(u,v)+2\delta$ follows from Claim 20. $\mathrm{⊲}$

Claims 19 and 21 yield the additive distance oracle (Item 1). Now we move on to a proof sketch of Item 2, whose complete proof can be found in the full version of the paper.

For a non-root $t\in V(T)$ we refer to its parent in $T$ as $\mathrm{𝗉𝖺𝗋𝖾𝗇𝗍}(t)$. For $u,v\in V(G)$ let $\mathrm{𝖺𝗉𝗑}\text{-}\mathrm{𝖽𝗂𝗌𝗍}(u,v)$ denote the value returned by the oracle from Claim 21 when queried for the pair $u,v$. This is a well-defined function because the oracle is deterministic. Recall the concept of an additive core-set from Lemma 1 and that $\tau =\mathrm{𝖽𝗂𝖺𝗆}(G)/\delta$.

The total number of distances we care about is $(w+1)\cdot {\sum }_{t\in V(T)}|V_t|=𝒪(w\cdot n\log n)$. Each of them can be estimated using the oracle in time $𝒪(w\log n)$. We would like to use those numbers to compute the additive core-sets, however a priori the bound from Lemma 1 might not hold for approximate distances. Nevertheless, we prove that a greedy procedure still constructs a small core-set, even after perturbation of distances. A similar issue is handled in [47] via randomization but we can afford a simpler argument because our strategy allows us to first query the oracle for all the distances between $V_t$ and $\chi (\mathrm{𝗉𝖺𝗋𝖾𝗇𝗍}(t))$.

In the next claim, we argue that the core-sets suffice to estimate the maximal distance between $v$ and $u$, where $v$ is fixed and $u$ is quantified over all vertices from some subtree. There are three sources of accuracy loss: relying on the additive core-set, on the approximate distance oracle, and stretching the paths along a center from $\chi (t)$ (Lemma 16).

We now use the additive core-sets to estimate the eccentricity of a vertex. Essentially, we apply Claim 23 for each choice of the lowest common ancestor of $v,u$; hence $𝒪(\log n)$ times.

Theorem 17(2) follows by applying Claim 24 to each vertex. $◀$

One can assume that $G$ is connected as otherwise the diameter is $\mathrm{\infty }$. We compute the eccentricity $D$ of an arbitrary vertex $v$: this can be done in linear time [52]. The diameter of $G$ must be contained in $[D,\mathrm{\hspace{0.17em}2}D]$. We apply Lemma 14 for $\delta =\epsilon D/16$ in time $𝒪(n\log n)$; let $𝒞$ denote the obtained $\delta$-radius clustering. Next, let $\tau =\mathrm{𝖽𝗂𝖺𝗆}(G)/\delta$; note that $\tau =𝒪(1/\epsilon )$. By Lemma 14(2) we know that $\mathrm{𝗍𝗐}(G_{𝒞})={𝒪}_h(1/\epsilon )$. We use Lemma 15 to build a binary tree decomposition of $\mathrm{𝗍𝗐}(G_{𝒞})$ of width $w={𝒪}_h({\epsilon }^{-2})$, depth $𝒪(\log n)$ and size $𝒪(n)$; this takes time ${𝒪}_h({\epsilon }^{-7}\cdot n\log n)$. Now we can take advantage of Theorem 17(2) to compute the eccentricities of all vertices within additive error $16\cdot \delta \le \epsilon \cdot \mathrm{𝖽𝗂𝖺𝗆}(G)$, together with vertices that realize these distance approximately. This takes time ${𝒪}_h(w^{h+1}\cdot {\tau }^h\cdot n{\log }^{2}n)={𝒪}_h({(1/\epsilon )}^{3h+2}\cdot n{\log }^{2}n)$. Finally, observe that $h$ is greater than 1 in any non-trivial instance so and so the time needed to compute the tree decomposition is negligible. $◀$