A Range Space with Constant VC Dimension for All-pairs Shortest Paths in Graphs
Vol. 27, no. 7, pp. 603-619, 2023. Regular paper.
Abstract Let $G$ be an undirected graph with non-negative edge weights and let $S$ be a subset of its shortest paths such that, for every pair $(u,v)$ of distinct vertices, $S$ contains exactly one shortest path between $u$ and $v$. In this paper we define a range space associated with $S$ and prove that its VC dimension is 2. As a consequence, we show a bound for the number of shortest paths trees required to be sampled in order to solve a relaxed version of the All-pairs Shortest Paths problem (APSP) in $G$. In this version of the problem we are interested in computing all shortest paths with a certain "importance" at least $\varepsilon$. Given any $0 < \varepsilon$, $ \delta < 1$, we propose a $\mathcal{O}(m + n \log n + (\textrm{diam}_{V(G)})^2)$ sampling algorithm that outputs with probability $1 - \delta$ the (exact) distance and the shortest path between every pair of vertices $(u, v)$ that appears as subpath of at least a proportion $\varepsilon$ of all shortest paths in the set $S$, where $\textrm{diam}_{V(G)}$ is the vertex-diameter of $G$. The bound that we obtain for the sample size depends only on $\varepsilon$ and $\delta$, and do not depend on the size of the graph.

 This work is licensed under the terms of the CC-BY license.
Submitted: December 2022.
Reviewed: April 2023.
Revised: June 2023.
Reviewed: July 2023.
Revised: August 2023.
Accepted: August 2023.
Final: September 2023.
Published: September 2023.
Communicated by Giuseppe Liotta
article (PDF)