# 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? – Ray Butterworth Aug 28 '20 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. – lchen Aug 28 '20 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? – fedja Aug 29 '20 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? – lchen Aug 29 '20 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? – fedja Aug 29 '20 at 14:28