Given a time-dependent graph, where each edge $e$ is on for certain time intervals and off otherwise. Traversing $e$ incurs a delay $d_e$ and is possible only when $e$ is on. Given a pair of vertices $v_s$ and $v_t$ and a time horizon from $0$ to $T$, we seek a path such that at any time $t\in[0,T]$ you depart from $v_s$, you can arrive at $v_t$ by time $t+D$, where $D$ is a parameter on the tolerable delay. Or in another formulation, for each path $P$ we can define its worst-case delay as the longest delay required to arrive at $v_t$ from $v_s$ for any departure time $t\in[0,T]$. We seek a path with minimal worst-case delay.
5
-
$\begingroup$ Does $t$ take only finitely many values? $\endgroup$– RobPrattCommented Oct 2, 2020 at 4:20
-
$\begingroup$ We may also consider the discrete scenario where $t\in \mathbb{Z}$. $\endgroup$– lchenCommented Oct 2, 2020 at 5:17
-
$\begingroup$ Is there a way to prove that the problem is NP-complete? $\endgroup$– lchenCommented Oct 11, 2020 at 12:34
-
$\begingroup$ This problem is not well defined at the moment. How is the time-dependency encoded in the input? Is $T$ in unary or given in binary? $\endgroup$– domotorpCommented Nov 15, 2020 at 6:25
-
2$\begingroup$ Thank you for your comment. Why is the problem not well-defined? Each edge $e$ is associated with a set of time intervals $[a_1,b_1],[a_2,b_2],\cdots$, during which the edge is ON. These intervals are given. $T$ is the time horizon, which is a real number. $\endgroup$– lchenCommented Nov 15, 2020 at 8:37
Add a comment
|