Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00636
A Range Space with Constant VC Dimension for Allpairs Shortest Paths in Graphs
Vol. 27, no. 7, pp. 603619, 2023. Regular paper.
Abstract Let $G$ be an undirected graph with nonnegative 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 Allpairs 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 vertexdiameter 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 CCBY 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

Journal Supporters
