# Shortest Path Centrality and the APSP problem via VC-dimension and Rademacher Averages

Preprint · Alane M. de Lima, Murilo V. G. da Silva, André L. Vignatti

- Archive id: arxiv:1911.13144
- Published: 2019-11-29
- arXiv: https://arxiv.org/abs/1911.13144
- Source URL: https://arxiv.org/abs/1911.13144
- PDF: https://arxiv.org/pdf/1911.13144
- Provenance: arxiv

## Abstract

In this paper we are interested in a version of the All-pairs Shortest Paths problem (APSP) that fits neither in the exact nor in the approximate case. We define a measure of centrality of a shortest path, related to the \`\`importance'' of such shortest path in the graph, and propose an algorithm based on the idea of progressive sampling that, for {\\it any fixed constants} $0 \< ε$, $ δ\< 1$, given an undirected graph $G$ with non-negative edge weights, outputs with probability $1 - δ$ a data structure of size $n \\cdot \\textrm{Diam}\_V(G)$, where $\\textrm{Diam}\_V(G)$ is the vertex diameter of $G$, in expected time $\\mathcal{O}(\\lg n \\max(m + n \\log n, n \\cdot \\textrm{Diam}\_V(G)))$ containing the (exact) distance and the shortest path between every pair of vertices $(u,v)$ that has centrality at least $ε$. The progressive sampling technique is sensitive to the probability distribution of the input (if we assume that $G$ is chosen from a prescribed random distribution), but even in the case where we take no assumption about such distribution, we show an upper bound for the sample size using VC-dimension theory that is tighter than the bound given by standard Hoeffding and union bounds, since VC-dimension theory captures the combinatorial structure of the input graph.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.