1 Introduction↩︎

For a sparse graph \(G\) with \(n\) vertices and \(O(n)\) non-negative real-weighted edges, it is possible to compute the diameter of \(G\) in \(\widetilde{O}(n^2)\) time² by running Dijkstra’s algorithm from every vertex of the graph. However, even in unweighted undirected graphs, computing the exact diameter in truly subquadratic time is impossible assuming the Strong Exponential Time Hypothesis (SETH) [7]. This negative result has motivated the study of diameter in structured graph classes where truly subquadratic-time diameter is achievable, such as bounded-treewidth graphs [8], [9], planar graphs [1], [2], bounded genus graphs [10], \(K_h\)-minor-free graphs [3]–[5], and geometric intersection graphs [6], [11].

Two major paradigms have emerged for breaking this quadratic barrier for structured graph classes. The first is abstract Voronoi diagrams for planar graphs that were pioneered by Cabello [1] and led to the first truly subquadratic-time diameter algorithm in planar graphs that ran in \(\widetilde{O}(n^{11/6})\) time. The running time was later improved to \(\widetilde{O}(n^{5/3})\) by Gawrychowski, Kaplan, Mozes, Sharir, and Weimann [2]. While abstract Voronoi diagrams easily extend to real-weighted and directed settings, the approach strongly relies on planarity and is likely only generalizable to bounded-genus graphs. The second paradigm revolves around VC-dimension. Ducoffe, Habib, and Viennot [3] demonstrated that it is possible to get a truly subquadratic-time algorithm in undirected unweighted \(K_h\)-minor-free graph with distance VC-dimension, the VC-dimension of neighborhood balls centered at every vertex of the graph. Le and Wulff-Nilsen [4] generalized a different bounded VC-dimension set system –distance profiles – studied by Li and Parter [12] in planar graphs to obtain results for directed \(K_h\)-minor-free graphs. Bounds on both distance VC-dimension and distance profiles were unified by Karczmarz and Zheng [5] with generalized distance VC-dimension³, that paved the way for improvements in more graph classes [6].

A striking discrepancy remains: Techniques using abstract Voronoi diagrams work in directed and real-weighted planar graphs [1], [2], [13], while techniques using VC-dimension results do not work well in real-weighted graphs. While the VC-dimension bounds directly generalized to real-weighted settings, and [4] extended the VC-dimension results to directed graphs, the existing algorithmic machinery did not seem to work well with real weights. The two limited results that did exist for weighted \(K_h\)-minor-free graphs either required integer weights with logarithmic dependence on the maximum weight [3], or achieved truly subquadratic space for a distance oracle at the cost of superquadratic construction time [5]. This motivates the central question of this paper: Is VC-dimension useful for truly subquadratic-time computation in real-weighted graphs?

1.1 Our Contribution↩︎

We answer our motivating question in the affirmative by giving the first algorithm for real-weighted diameter computation in \(K_h\)-minor-free digraphs. Our result generalizes to any monotone graph family with strongly sublinear-sized balanced separators, a family equivalent to graphs of polynomial expansion [14]. We show that if the generalized distance VC-dimension is bounded, we can compute the vertex eccentricities (and thus diameter) of the graph in truly subquadratic time. See ¿tbl:tab:graph-algorithms? for a comparison of our results to previous algorithms.

\(K_h\)-minor-free graphs are a special subclass of graphs with polynomial expansion as they are a monotone graph class with \(\beta=1/2\) (i.e. they have \(O(\sqrt{n})\) sized separators). They also have generalized distance VC-dimension at most \(h-1\) [5], so the corollary follows.

The previous algorithm of [3] computed all vertex eccentricities with a decision procedure: given a guess \(\ell_u\) on the eccentricity of every vertex \(u\) in the graph \(G\), outputs whether \(\ell_u\) is an over- or under-estimate of the true eccentricity of \(u\). Using this procedure, it is easy enough to binary search for the eccentricities of every vertex in graphs where edges have small integer weight, or to obtain \((1+\varepsilon)\)-approximations. Unfortunately, this binary search fails to yield exact results for real-weighted graphs since there can be exponentially many distances.

To bypass this limitation, we augment the decision procedure to output random witnesses. To be precise, if a guess \(\ell_u\) for the eccentricity of \(u\) is an underestimate, the algorithm should additionally output a random witness \(v\) whose distance from \(u\) is larger than \(\ell_u\). By transforming the simple decision oracle to a random witness producing oracle, we reduce the search for the real-valued eccentricity to a small number of augmented oracle calls. See 3 for the full details. We present the entire algorithm in 4 by extending and significantly simplifying the decision algorithm of [3].

2 Preliminaries↩︎

Throughout this paper, we will consider a directed graph \(G = (V,E)\) with \(n=|V|\) vertices and positive real weights on all edges. For two vertices \(u,v\in V\), we denote the length of the shortest directed path from \(u\) to \(v\) in \(G\) as \(d_G(u\to v)\). For convenience, we will assume throughout this paper that there is a unique shortest path between any two vertices \(u, v\in V\). Note that for any graph \(G\) that does not have unique shortest paths, we may apply (tiny) perturbed weights to every edge in \(G\) to create a new graph where shortest paths are unique and shortest paths in this new graph are also shortest paths in \(G\). This can be done in many ways, e.g., with the Isolation Lemma [15]. For any \(k\in \mathbb{R}\), define the \(k\)-neighborhood ball (or \(k\)-neighborhood for short) of a vertex \(u\in V\) to be the set of vertices that are reachable from \(u\) and at distance at most \(k\) from \(u\), denoted by \(N^k_G[u] = \{v\in V\mid d_G(u\rightarrow v) \le k\}\). The eccentricity of a vertex \(u\in G\) is the maximum distance from \(u\) to any other vertex, and is denoted by \(\mathrm{ecc}(u) = \max_v d_G(u\to v)\). The diameter of the graph \(G\) is the maximum eccentricity of any vertex, i.e. \(\max_v \mathrm{ecc}(v)\). For simplicity, all graphs throughout this paper will be strongly connected unless otherwise specified. If the graph \(G\) is not strongly connected, then there may not be a directed path from \(u\) to \(v\) and the distance \(d_G(u\to v)\) is not well-defined. In this case, it is possible to define the eccentricity of a vertex \(u\) to be the distance to the farthest reachable vertex.

3 Random Witnesses for Eccentricity↩︎

In this paper, we will focus on the problem of computing eccentricity of every vertex, as diameter can be easily computed by taking the maximum eccentricity among all vertices. We begin by considering an algorithm to compute the eccentricity of a single vertex.

Single Vertex Eccentricity

Fix one \(u\in V\), and suppose we have a guess for its eccentricity \(\ell_u\). Suppose we had an algorithm \(\mathcal{A}\) for deciding if the eccentricity of \(u\) was at most \(\ell_u\). Suppose our guess was an underestimate, i.e. that \(\ell_u < \mathrm{ecc}(u)\). It is reasonable to expect the algorithm \(\mathcal{A}\) to give a witness \(w\in V\) that proves that \(\ell_u\) is smaller than the eccentricity of \(u\), meaning that \(\ell_u < d_G(u\to w)\). We can use \(d_G(u\to w)\) as a new guess \(\ell'_u = d_G(u\to w)\) for the eccentricity, and run the algorithm \(\mathcal{A}\) again.

We use the following notation to denote the set of vertices at distance strictly greater than \(k\) away from vertex \(u\). \[N^{> k}_G[u] = \{v\in V\mid d(u\to v) > k\}\] \(N^{> \ell_u}_G[u]\) is exactly the set of witnesses that \(\mathcal{A}\) could have chosen, so \(w\in N^{> \ell_u}_G[u]\). When we run the algorithm \(\mathcal{A}\) on our new guess \(\ell'_u\), we would get a new witness from \(N^{>\ell'_u}_G[u]\). Observe that \(N^{>\ell'_u}_G[u] \subset N^{>\ell_u}_G[u]\) (the inclusion is strict). It is possible that \(|N^{>\ell'_u}_G[u]| = |N^{\ell_u}_G[u]|-1\), so very little progress was made. This could occur if we were unlucky or the algorithm \(\mathcal{A}\) was adversarial. On the other hand, if the algorithm \(\mathcal{A}\) gave us a random witness, we would expect that \[\mathop{\mathbb{E}}\left[|N^{>\ell'_u}_G[u]|\right]=\frac{1}{2}|N^{>\ell_u}_G[u]|.\] It is easy to see that by repeatedly finding a random witness, we would expect to find the vertex of maximum distance from \(u\) in \(O(\log |N^{>\ell_u}_G[u]|) = O(\log n)\) many rounds. It is folklore that this bound additionally holds with high probability⁴. For completeness, we present the following proof based on backwards analysis [16].

Multiple Vertex Eccentricity

Suppose we had a guess \(\ell_u\) on the eccentricity of every vertex \(u\in V\) that is an underestimate (so \(\ell_u<\mathrm{ecc}(u)\)), as well as an algorithm \(\mathcal{A}\) for deciding the guess of every \(\ell_u\) simultaneously and also returns a random witness for every \(\ell_u\). By a simple union bound with 1, we will find the eccentricity of every vertex in at most \(O(\log n)\) rounds with high probability.

In the next section, we show an algorithm that simultaneously returns a random witness for every vertex that runs in truly subquadratic time provided the graph has strongly sublinear-sized balanced separators and bounded generalized distance VC-dimension (for definitions see 4.1).

4 Eccentricity Algorithm↩︎

4.1 Definitions↩︎

We begin with definitions of graph separators, VC-dimension, and low average crossing spanning paths that are important tools.

Graph classes, balanced separators, and \(r\)-divisions.

A graph class is monotone if it is closed under taking subgraphs. For a graph \(G\) with \(n\) vertices, a balanced separator is a set of vertices \(S\) such that every connected component of \(G \setminus S\) has size at most \(2n/3\).

Let \(\mathcal{G}_\beta\) be a monotone graph class such that any \(n\)-vertex graph \(G\in \mathcal{G}_\beta\) has \(O(n^\beta)\)-sized balanced separators. Note that all such graphs \(G\in \mathcal{G}_\beta\) are sparse [14], i. e. if \(G\) has \(n\) vertices, \(G\) has \(O(n)\) edges. In \(n\) vertex \(K_h\)-minor-free graphs, recent work of [18] show that balanced \(O(\sqrt{n})\)-sized balanced separators can be computed in linear time. In general graphs, recent work of [19] show that balanced separators of nearly-optimal size can be efficiently computed by a black-box reduction to maximum flow, which can be solved in \(m^{1+o(1)}\) time in \(m\)-edge graphs [20].

A piece \(P\subseteq V\) of a graph is a subset of vertices such that the induced graph \(G[P]\) is connected. An \(r\)-division is a set of pieces \(P_1, P_2, \dots, P_k\) each with at most \(r\) vertices such that \(V = \bigcup_{i=1}^k P_i\), and for every two pieces \(P_i\) and \(P_j\), the vertices \(P_i \setminus P_j\) and \(P_j \setminus P_i\) have no edges between them (they may share some vertices). For a piece \(P\), the vertices with edges to \(G\setminus P\) we refer to as boundary vertices, while all other vertices in \(P\) we refer to as interior vertices. Let \(\partial\!P\) denote the set of boundary vertices of a piece \(P\). The total boundary of the \(r\)-division is the quantity \(\sum_{i=1}^k |\partial\!P_i|\). The idea of \(r\)-divisions was originally introduced by Frederickson [21] by using sublinear-sized balanced separators for planar graphs⁵. The algorithm is now standard: recursively find balanced separators until each component has size at most \(r\). The algorithm is efficient as 3 runs in near-linear time as all graphs in \(\mathcal{G}_\beta\) are sparse.

VC-dimension

A set system \((X, \mathcal{S})\) is a ground set \(X\) together with a collection \(\mathcal{S}\subseteq 2^{X}\) of subsets of the ground set \(X\). For a subset \(Y\subseteq X\), we denote by \(\mathcal{S}_{| Y}\) to be the set of \(\mathcal{S}\) restricted to \(Y\), that is \(\mathcal{S}_{|Y} = \{Y\cap S\mid S\in \mathcal{S}\}\). The set \(Y\) is shattered by \(\mathcal{S}\) if \(|\mathcal{S}_{|Y}| = 2^{|Y|}\). The shatter function of a set, denoted by \(\pi_{(X,\mathcal{S})}(h)\), is the largest number value of \(|\mathcal{S}_{\mid Y}|\) among all size-\(h\) subsets \(Y\subseteq X\). The shatter dimension of the set system \((X, \mathcal{S})\) is the smallest value of \(d\) such that \(\pi_{(X,\mathcal{S})}(h) = O(h^d)\) for all \(h\). The VC-dimension of the set system \((X, \mathcal{S})\) is the size of the largest subset \(Y\subseteq X\) that can be shattered by \(\mathcal{S}\). The dual set system is the set system \((\mathcal{S}, X^*)\) where the ground set is indexed by \(\mathcal{S}\), and each element \(x\in X\) induces a set \(x^*\in X^*\) consisting of the ground set elements \(x^* = \{S\in \mathcal{S}\mid S\ni x\}\). The dual VC-dimension is the VC-dimension of the dual set system, and the dual shatter dimension is the shatter dimension of the dual set system. We list two known facts about VC-dimension.

Generalized distance VC-dimension

Recall that for a vertex \(u\) in a graph \(G\), the notation \(N^k_G[u]\) denotes the set of vertices within a distance \(k\in \mathbb{R}\) from \(u\). We denote the set of all neighborhood balls as \(\mathcal{B}_G = \{N^k_G[v]\mid v\in V, k\in \mathbb{R}\}\). The distance VC-dimension of a (weighted) digraph \(G=(V,E)\) is the VC-dimension of the set system \((V, \mathcal{B}_G)\). Generalized \(k\)-neighborhood balls \(M^k_G[u] = \{(v, r)\in V\times \mathbb{R}\mid d(u\to v) \le r + k\}\) were studied by [5] and considered in [6]. One way to think about \(M^k_G[u]\) is that it contains \((v, r)\) for all values of \(r\) where \(r \ge d(u\to v)-k\). The set of all generalized neighborhood balls in \(G\) is denoted by \(\mathcal{M}_G = \bigcup_{k,v} M_G^k[v]\). This allows us to define the generalized distance VC-dimension of a weighted digraph \(G = (V, E)\) as the VC-dimension of the set system \((V\times \mathbb{R}, \mathcal{M}_G)\).

One benefit of this definition is that the generalized distance VC-dimension bound is an upper bound on the dual VC-dimension of \((V, \mathcal{B}_G)\), which we call the dual distance VC-dimension. This is used by [6], although its proof is not explicitly stated. For completeness we prove it here.

Generalized distance VC-dimension is natural to consider as both \(K_h\)-minor-free (di)graphs [5] and geometric intersection graphs [22] have bounded generalized distance VC-dimension.

Low average crossing spanning paths

Consider a set system \((X,\mathcal{S})\) with \(|X|=n\) and \(|\mathcal{S}| = m\), and an ordering \(\lambda\) of the elements of \(X\). For an \(S\in \mathcal{S}\), define intervals to be the maximal contiguous subsequences of \(S\) in \(\lambda\). We denote the set of these intervals (whose union is \(S\)) as \(\sf Rep_\lambda(S)\) and call this the \(\lambda\)-interval representation of \(S\). The ordering is said to cross (or stab) \(S\) if \(\lambda_i \in S\) but \(\lambda_{i+1} \not \in S\), or \(\lambda_i \not\in S\) but \(\lambda_{i+1} \in S\) (this ordering is sometimes called a stabbing path). Note that the number of crossings is proportional to \(|\sf Rep_\lambda(S)|\). A low average crossing spanning path is an ordering \(\lambda\) where each set \(S\in \mathcal{S}\) is on average crossed a small number of times. This is weaker than the original notion of low crossing spanning paths introduced by Chazelle and Welzl [23], [24] that guarantees every set is crossed a sublinear number of times. It was proven in [11] and [6] that these low average crossing spanning paths can be efficiently constructed with high probability.

4.2 Eccentricities Algorithm↩︎

Here we describe the algorithm for computing the eccentricity of every vertex of a strongly connected \(n\)-vertex graph \(G=(V,E)\) with \(G \in \mathcal{G}_\beta\) where \(\mathcal{G}_\beta\) is a monotone graph class with \(O(n^\beta)\)-sized balanced separators and \(G\) has generalized distance VC-dimension \(d\).

We first give a high level overview of the algorithm. The algorithm computes an \(r\)-division (for a value of \(r\) we will specify later) and tries to compute the eccentricity of a vertex \(u\) in a piece \(P_i\). The eccentricity will either be achieved strictly within the piece \(P_i\), or it will be achieved by some path through a boundary vertex of \(P_i\). The first case is easily handled since \(P_i\) has at most \(r\) vertices and we can afford to compute distances within \(G[P_i]\). The second case can be handled as we can afford to compute shortest paths from all boundary vertices. This leads to the following equality: \[\label{eq:nbhd} N_G^{\ell_u}[u] = N^{\ell_u}_{G[P_i]}[u] \cup \bigcup_{v\in \partial\!P_i} N_G^{\ell_u-d_G(u\to v)}[v].\tag{1}\] Note that if \(c\) is negative, then \(N_G^c[v]\) is defined to be the empty set. This union can be constructed efficiently with a low average crossing spanning path \(\lambda\), and there are at most \(r\) additional elements of \(N^{\ell_u}_{G[P_i]}[u]\) that can be manually added. We can use a single (global) low average crossing spanning path as we construct all these neighborhood balls.

Algorithm for all vertex eccentricities

Here we present the algorithm for computing all vertex eccentricities. We remark that steps 5(a)-5(c) closely resemble the algorithm of [3], and 5(d) is the main contribution of this paper.

1. Compute an \(r\)-division resulting in pieces \(P_1, P_2, \dots, P_k\) with total boundary size \(\widetilde{O}(n/r^{1-\beta})\).

2. Let \(V_{in}\subset V\) denote the set of internal vertices of the \(r\)-division. For every piece \(P_i\), compute the shortest path between every internal vertex \(u\in V_{in}\) and all other vertices in \(P_i\) where distances are computed within the graph \(G[P_i]\).

3. For every vertex \(v\) that is a boundary vertex of any piece, compute the distance from \(v\) to every vertex of \(V\) in \(G\).

4. Initialize a vector of guesses to eccentricity \((\ell_u)_{u\in V_{in}}\) where \(\ell_u=0\) for all \(u\in V_{in}\).

5. Repeat the following procedure for all vertices simultaneously (that either finds a random witness disproving that the eccentricity is \(\ell_u\), or concludes that \(\mathrm{ecc}(u) = \ell_u\)).

   1. Consider the neighborhood balls centered at boundary vertices \(v\in \partial\!P_i\) with distance \(\ell_u-d(u\to v)\) for every internal vertex \(u\in V_{in} \cap P_i\). Define the following (multiset) of balls: \[\mathcal{B}^{out}_i = \left\{N_G^{\ell_u-d(u\to v)}[v] \biggm\vert u\in V_{in}\cap P_i, v\in \partial\!P_i\right\}\] Consider the multiset \(\mathcal{D}= \bigcup_{i=1}^k \mathcal{B}^{out}_i\). Compute a low average crossing spanning path \(\lambda\) for the set system \((V, \mathcal{D})\).

   2. For each piece \(P_i\), each boundary vertex \(v\in \partial\!P_i\), and each neighborhood ball \(N^t_G[v]\in \mathcal{B}_i^{out}\), compute the \(\lambda\)-interval representation \(\sf Rep_\lambda(N^t_G[v])\) in increasing order of radius \(t\).

   3. For each piece \(P_i\), and each internal vertex \(u\in V_{in}\cap P_i\), use 1 to compute the \(\lambda\)-interval representation \(\sf Rep_\lambda (N_G^{\ell_u}[u])\).

   4. For each internal vertex \(u\in V_{in}\), if \(\sf Rep_\lambda (N_G^{\ell_u}[u])\) is an interval consisting of all vertices, we conclude that the eccentricity is \(\ell_u\). Otherwise, we can sample a random witness \(w\in V\setminus N_G^{\ell_u}[u]\) by using the interval representation \(\sf Rep_\lambda (N_G^{\ell_u}[u])\), and update \(\ell_u\) to be the value \[d_G(u\to w)= \min\left\{d_{G[P_i]}(u\to w),\min_{v\in \partial\!P_i} d_{G[P_i]}(u\to v) + d_G(v\to w)\right\}\label{eq:dist}\tag{2}\] where \(d_{G[P_i]}(u\to w) = \infty\) if \(w\) is not a vertex of \(P_i\).

Correctness

We can easily read off the eccentricity of the boundary vertices since we computed all distances from boundary vertices in step 3. For a non-boundary vertex \(u\in V_{in}\cap P_i\), the initial guess of \(\ell_u = 0\) is an obvious lower bound for eccentricity and \(\ell_u\) stays a lower bound for eccentricity as it changes in step 5d. Furthermore, it can only increase. The correctness of 1 means that accurate neighborhood balls are computed at the end of step 5c. The argument that paths must lie entirely within some \(P_i\) or must intersect a boundary vertex also shows correctness of 2 for efficient computation of distances to random witnesses.

Runtime

Step 1 takes \(n^{1+o(1)}\) time by 4. Step 2 takes \(\widetilde{O}(r)\) time using Dijkstra’s algorithm for each internal vertex \(u\in P_i\) since the induced graph \(G[P_i]\) has \(r\) vertices and \(O(r)\) edges, for a total of \(\widetilde{O}(nr)\) time for all internal vertices. Step 3 takes \(\widetilde{O}(n)\) time for performing Dijkstra’s algorithm per boundary vertex for a total of \(\widetilde{O}(n)\cdot \widetilde{O}(n/r^{1-\beta}) = \widetilde{O}(n^2/r^{1-\beta})\) time. Step 5 is repeated at most \(O(\log n)\) times with high probability by 2. Step 5a takes \(\widetilde{O}(n^{1+1/d})\) time using 6 since we can enumerate any of the desired neighborhood balls in \(\widetilde{O}(n)\) time with Dijkstra’s algorithm. Note that this running time is independent of the number of sets \(m = |\mathcal{D}|\) that we had in our set system. \[m = |\mathcal{D}| = \sum_{i=1}^k|\mathcal{B}_i^{out}| = \sum_{i=1}^k|P_i|\cdot |\partial\!P_i|\le O(r)\cdot \sum_{i=1}^k |\partial\!P_i| = \widetilde{O}(nr^{\beta})\] Step 5b can be implemented in the following fashion: when computing the neighborhood balls of various radii for a vertex \(v\), go in order of increasing radii and only add vertices to the maintained \(\lambda\)-interval representation. This can be done incrementally one vertex at a time using the distance information we computed in step 3. Merging any inserted vertex with any adjacent intervals takes \(O(1)\) time per insertion. The total amount of time taken for this step at most \(\widetilde{O}(n^2/r^{1-\beta})\). Step 5c can be implemented for a vertex \(u\in V_{in}\cap P_i\) by sorting the end points of the intervals of \(\sf Rep_\lambda(N_G^{\ell_u - d_G(u\to v)}[v])\) for all \(v\in \partial\!P_i\) and doing a line sweep to merge the intervals. The \(N_{G[P_i]}^{\ell_u}[u]\) term can be directly computed from step 2 and added to the representation since there are at most \(r\) vertices. By the guarantee of 6, this takes time at most \[\begin{align} \sum_{i=1}^{k} \sum_{u\in P_i\cap V_{in}} \widetilde{O}\left(|P_i|+ \sum_{v\in \partial\!P_i} |\sf Rep_\lambda(N_G^{\ell_u-d_G(u\to v)}[v])|\right) &= \widetilde{O}(nr) + \sum_{B\in \mathcal{B}_i^{out}} \widetilde{O}(|\sf Rep_\lambda(B)|) \\ &= \widetilde{O}(nr + mn^{1-1/d}) \\ &= \widetilde{O}(nr +n^{2-1/d}r^{\beta}). \end{align}\] In step 5d, the sampling can be implemented for a vertex \(u\in V_{in}\cap P_i\) in time proportional to the complexity of the union of intervals computed in 5c, which is \(\widetilde{O}(n^{2-1/d}r^\beta)\) time. Computing the distances to its witness using 2 for each vertex takes a total of \(\widetilde{O}(nr^{\beta})\) time by the same analysis as for \(m\) using the distances computed in step 2 and step 3.

The total running time is minimized by setting \(r=n^{1/d}\). \[\widetilde{O}(n^{1+o(1)}+nr + n^2/r^{1-\beta} +n^{1+1/d} + n^{2-1/d}r^{\beta}) = \widetilde{O}(n^{2-(1-\beta)/d}).\] We conclude the following theorem.

4.3 Variations↩︎

Bounded distance VC-dimension.

If the graph \(G\) does not have bounded generalized distance VC-dimension, but instead bounded distance VC-dimension, we can still bound the dual distance VC-dimension (and thus shatter dimension) by 5(3) by \(2^{d+1}\). This still leads to a truly subquadratic-time algorithm for real-weighted eccentricities, although the running time becomes \(\widetilde{O}(n^{2-(1-\beta)/2^{d+1}})\).

Farthest reachable vertex.

If the graph \(G\) is not strongly connected, we can still compute the farthest reachable vertex from every vertex in the same running time. To do this, we need to modify step 5(d). For a vertex \(u\), instead of checking if the \(\lambda\)-interval representation \(\sf Rep_\lambda(N_G^{\ell_u}[u])\) consists of all vertices, we need to check if it consists of all reachable vertices from \(u\), and sample only among the reachable vertices. The reachable vertices from \(u\) can be thought of as \(N_G^{\infty}[u]\) – the set of vertices reachable from \(u\) at an arbitrary distance from \(u\). A \(\lambda\)-interval representation \(\sf Rep(N_G^{\infty}[u])\) can be computed from the set of vertices within the piece \(P_i\) that \(u\) is in (at most \(r\) many vertices), as well as \(N_G^\infty[v]\) for all vertices \(v\in \partial\!P_i\). If we add \(N_G^\infty[v]\) to \(\mathcal{D}\) before the computation of \(\lambda\), they would have low average crossing number, and would allow us to compute the \(\lambda\)-interval representation of the set of reachable vertices \(\sf Rep_\lambda(N^\infty_G[u])\) using the following identity: \[N^{\infty}_G[u] = N_{G[P]}^{\infty}[u] \cup \bigcup_{v\in \partial\!P} N^\infty_G[v]\] Now we can efficiently sample from \(N_G^{\infty}[u] \setminus N_G^{\ell_u}[u]\) by a line sweep through the end points of the \(\lambda\)-interval representations of the two. The overall runtime is unchanged.

5 Conclusion↩︎

In this paper, we have shown that VC-dimension techniques can be used to compute real-weighted diameter in truly subquadratic time in minor-free graphs and other graphs that have sublinear-sized balanced separators and bounded distance VC-dimension. One downside is that the algorithm does not work for computing other quantities such as Wiener index. The algorithm described in [3] faces the same issue.

Another downside of the result is the reliance on sublinear-sized balanced separators. The results of [6] bypass the need for sublinear-sized balanced separators in the unweighted setting by using low diameter decompositions. This relied on an alternate algorithm for diameter that runs in truly subquadratic time in unweighted graphs of small diameter. However, it is unclear if such a low diameter algorithm exists in the real-weighted setting.

References↩︎