Undirected Replacement Paths: Dual Fault Reduces to Single Source

Jakob Nogler, Virginia Vassilevska Williams

Given a graph and two fixed vertices $s$ and $t$, the Replacement Path Problem (RP) is to compute for every edge $e$, the distance between $s$ and $t$ when $e$ is removed. There ar…