A Range Space with Constant VC Dimension for All-pairs Shortest Paths in Graphs - de Lima, Alane; da Silva, Murilo; Vignatti, André (Journal of Graph Algorithms and Applications, 2023)
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 $ε$. Given any $0 < ε$, $ δ < 1$, we propose a $\mathcal{O}(m + n \log n + (diam_{V(G)})^2)$ sampling algorithm that outputs with probability $1 - δ$ the (exact) distance and the shortest path between every pair of vertices $(u, v)$ that appears as subpath of at least a proportion $ε$ of all shortest paths in the set $S$, where $diam_{V(G)}$ is the vertex-diameter of $G$. The bound that we obtain for the sample size depends only on $ε$ and $δ$, and do not depend on the size of the graph.