We will research variants of shortest paths algorithms and data-structures in setting with failures as well as fixed-parameter tractable algorithms in settings with failures, as described below.
(1) We study variants of shortest paths algorithms and data-structures in setting with failures. In particular, we study the Replacement Paths Problem (RP), where given a graph G with n vertices and m edges and let P be a shortest path from s to t in G the replacement paths problem is to compute for every edge e in P the shortest path from s to t avoiding e.
The goal of this research direction is to construct efficient algorithm and data-structures for computing both exact and approximate replacement paths in various settings, and derandomize existing optimal randomized algorithms for these problems.
(2) Fault-Tolerant Fixed Parameter Tractable Algorithms – the goal in this research direction is to develop efficient algorithms and data-structures to solve fixed-parameter tractable algorithms (such as k-path, vertex cover, maximum independent set, etc.) in settings with failures. Upon a failure, it is inefficient to re-compute in exponential time the solution to the fixed-parameter tractable problem. Instead to goal is preprocess the graph in exponential time, and then upon failure to compute the solution in polynomial or even poly-logarithmic time.
Here are some references for examples:
Shortest Paths Problems:
[1] (1+epsilon)-Approximate f-Sensitive Distance Oracles, by Shiri Chechik, Sarel Cohen, Amos Fiat, and Haim Kaplan, published in SODA 2017.