CanaDAM 2021
On-line, May 25 - 28, 2021

Scheduling and Algorithms

ALANE DE LIMA, Federal University of Paraná (UFPR)
Sample Complexity in Graph Problems  [PDF]

We present the use of sample complexity tools in two randomized algorithms for graph problems. We first show a $\tilde{\mathcal{O}}(m)$ algorithm for a directed weighted graph $G$ that, for $0 < \epsilon,\delta < 1$, it estimates the percolation centrality of every vertex of $G$ within $\epsilon$ of the original value with probability at least $1-\delta$. The second problem we deal with is the all-pairs shortest paths problem (APSP) for undirected graphs with non-negative real weights. We propose an algorithm that computes the exact shortest path SP between a pair of vertices depending on a certain measure of “importance” of SP, called shortest path centrality. That is, for $0 < \epsilon,\delta < 1$, SP is computed with probability at least $1-\delta$ whenever its centrality is at least $\epsilon$. The algorithm has expected running time $\mathcal{O}(\log \textrm{Diam}_V(G) \cdot \max(m + n \log n, \textrm{Diam}_V(G)^2))$, where $\textrm{Diam}_V(G)$ is the vertex-diameter of G.