Given a graph $G=(V,E)$ and a pair of source-destination nodes $s$ and $t$. Time is divided in periods with the total number of periods denoted by $T$. Each edge $e$ is either operational or broken at each period $\tau$. A path is *good* at period $\tau$ if all its edges are operational at period $\tau$. Suppose we cannot find a path that is good for the entire $T$ periods. We seek a pair of node-disjoint paths such that at least one of them is good at each period $\tau$. What is the hardness of this problem? Is it related to some known problem? Any suggestion in developing algorithm to find the good path pair?

$\begingroup$
$\endgroup$

14
9more comments