2020/02/26 by Udit Agarwal, Agarwal, Udit
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2002.11617
openalex publication_date 2020/02/26 · openalex created_date 2020/03/06 · openalex updated_date 2026/07/28
We present the first polynomial time algorithm for the f vertex fault tolerant spanner problem, which achieves almost optimal spanner size. Our algorithm for constructing f vertex fault tolerant spanner takes O(k⋅ n⋅ m2 ⋅ W) time, where W is the maximum edge weight, and constructs a spanner of size O(n1+1/kf1-1/k⋅ (log n)1-1/k). Our spanner has almost optimal size and is at most a log n factor away from the upper bound on the worst-case size. Prior to this work, no other polynomial time algorithm was known for constructing f vertex fault tolerant spanner with optimal size. Our algorithm is based on first greedily constructing a hitting set for the collection of paths of weight at most k ⋅ w(u,v) between the endpoints u and v of an edge (u,v) and then using this set to decide whether the edge (u,v) needs to be added to the growing spanner.