  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 $O(f^{1-1/k} n^{1+1/k})$ edges resilient to $f$ vertex
faults, and there are examples of input graphs on which this bound cannot be
improved. However, these proofs work by analyzing the output spanner of a
certain exponential-time greedy algorithm. In this work, we give the first
algorithm that produces vertex fault tolerant spanners of optimal size and
which runs in polynomial time. Specifically, we give a randomized algorithm
which takes $\widetilde{O}\left( f^{1-1/k} n^{2+1/k} + mf^2\right)$ time. We
also derandomize our algorithm to give a deterministic algorithm with similar
bounds. This reflects an exponential improvement in runtime over [Bodwin-Patel
PODC '19], the only previously known algorithm for constructing optimal vertex
fault-tolerant spanners.
