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$ Is the given G guaranteed to contain a good path pair? $\endgroup$ Aug 28, 2020 at 12:40
  • $\begingroup$ @RayButterworth Not necessarily. In fact we can formulate the entire problem as (1) decide the existence of such path pair (2) find them. $\endgroup$
    – lchen
    Aug 28, 2020 at 12:43
  • 1
    $\begingroup$ 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? $\endgroup$
    – fedja
    Aug 29, 2020 at 6:12
  • 1
    $\begingroup$ @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? $\endgroup$
    – lchen
    Aug 29, 2020 at 10:04
  • 1
    $\begingroup$ 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? $\endgroup$
    – fedja
    Aug 29, 2020 at 14:28


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.