Let G=(V,E) be an undirected unweighted graph. A path between any two vertices u,v∈V is said to be t‐approximate shortest path if its length is at most t times the length of the shortest path between u and v. We address the problem of building a compact data structure which can efficiently answer the following query for any u,v,x∈V and t>1:
Report t‐approximate shortest path between u and v when vertex x fails.
We present data structures for the single source as well as all‐pairs versions of this problem. The query time guaranteed by our data structures is optimal up to a constant factor. Moreover, the size of each of them nearly matches the size of the corresponding data structure with no failures.
