A Range Space with Constant VC Dimension for All-pairs Shortest Paths in Graphs

摘要

© 2023, Brown University. All rights reserved.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 log n + (diamV(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 diamV(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.