Optimal Vertex Fault-Tolerant Spanners in Polynomial Time

Greg Bodwin, Michael Dinitz, Caleb Robelle

Recent work has pinned down the existentially optimal size bounds for vertex fault-tolerant spanners: for any positive integer $k$, every $n$-node graph has a $(2k-1)$-spanner on $…