# Disjoint paths in temporal graphs

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?

• Is the given G guaranteed to contain a good path pair? Aug 28, 2020 at 12:40
• @RayButterworth Not necessarily. In fact we can formulate the entire problem as (1) decide the existence of such path pair (2) find them. Aug 28, 2020 at 12:43
• sciencedirect.com/science/article/pii/S1572528612000035 looks like a bad news (NP-complete even for $T=2$, see Lemma 2). The killer seems to be the requirement that the paths have to be vertex disjoint. Do you really need it? Aug 29, 2020 at 6:12
• @fedja Thank you very much for the reference (the result is not surprising to me). Is there any nice algorithm if the disjointness constraint is relaxed? Aug 29, 2020 at 10:04
• Only if $T$ is small, but then it is trivial. If $T$ is allowed to be comparable to $|V|$, you can enforce the vertex disjointness by introducing $|V|$ extra periods in each of which one intermediate vertex is blocked but all other edges remain open. What are the actual numbers $|V|,|E|,T$ you are thinking of? Aug 29, 2020 at 14:28