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 O(m + n 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.