Given a graph $G=(V,E)$. The cost of each edge $e$ is a function of time, denoted by $w_e(t)$. Given a time interval $[0,T]$, for any path $P$ starting at $v_s$ at time $t\in[0,T]$, we denote $t_e^P$ the time an edge $e\in P$ is traversed. We ignore the time to pass $e=(u,v)$, i.e., at time $t_e^P$, we go from $u$ to $v$ with a cost $w_e(t)$. We may choose to wait for a certain time at any vertex. Let $w_P(t)=\sum_{e\in P} w_e(t_e^P)$ denote the cost of $P$ when starting from $v_s$ at time $t$. We seek a $v_s-v_t$ path $P$ to minimize $\max_{t\in[0,T]} w_P(t)$. How to approach this problem?
-
$\begingroup$ One way is to define Ricci flow on Graphs by the Olliver-Ricci curvature and the Forman-Ricci curvature $\endgroup$– user160903Sep 16, 2020 at 15:23
-
$\begingroup$ Thank you for the comment, but I am interested in algorithms solving the problem, instead of abstract math formulation. $\endgroup$– lchenSep 17, 2020 at 1:34
-
$\begingroup$ Should the summand $c_e(t_e)$ instead be $w_e(t_e^P)$? $\endgroup$– RobPrattSep 20, 2020 at 13:47
-
$\begingroup$ @RobPratt Thank you for pointing out. I have corrected the typo. $\endgroup$– lchenSep 20, 2020 at 14:11
-
$\begingroup$ Also, $v_t$ is just the sink node and the subscript has nothing to do with time $t$? $\endgroup$– RobPrattSep 20, 2020 at 14:17
2 Answers
Call $P$ an $\varepsilon$-path if $\max_{t\in[0,T]}w_P(t)\leq\varepsilon$. Define the duration of a path as the maximum $t_e^P$ over all edges $e$ on $P$. For a vertex $u$, let $\tau_\varepsilon(u)$ be the infimum duration over all $\varepsilon$-path from $v_s$ to $u$. Consider the problem of deciding whether an $\varepsilon$-path from $v_s$ to $v_t$ exists; that is, deciding whether $\tau_\varepsilon(v_t)\leq T$. For any fixed $\varepsilon$, you can compute the values of $\tau_\varepsilon(u)$ for any vertex $u$ (and in particular $v_t$) using a modified version of Dijkstra's algorithm: use a priority queue that is initialized with the source vertex $v_s$ with priority $0$, using the invariant that enqueued vertices have a $\varepsilon$-path whose duration is their priority. When popping a vertex $u$ from the queue for the first time, say with priority $t$, set $\tau_\varepsilon(u):=t$, and enqueue all the neighbors $v$ with priority $t_{(u,v)}$, where $t_{(u,v)}$ is the first time $\geq\tau_\varepsilon(u)$ for which $w_{(u,v)}(t_{(u,v)})\leq\varepsilon$.
For the optimization version, observe that the optimum value of $\varepsilon$ can occur at the intersection of two functions $w_e$ and $w_{e'}$, or a local minimum of a single function $w_e$, or the value of a function $w_e$ at $t=0$ or $t=T$. So, taking into account the complexity of the functions $w_e$, there are only quadratically many candidate values for the optimum $\varepsilon$, which you can compute and binary search on using the decision problem.
-
$\begingroup$ Thank you. If we require that the path delay be upper-bounded by say $T'$ (basically we cannot wait too long), the optimization problem cannot be solved exactly. Am I correct? $\endgroup$– lchenSep 22, 2020 at 6:30
-
$\begingroup$ I assume that by path delay, you mean the time between consecutive edges. If we are not allowed to revisit vertices, it is probably NP-hard to compute. If we are allowed to revisit vertices I'm not sure; you might still be able to solve it by storing the time-intervals for which you can enter a vertex, instead of the earliest time you can enter a vertex. $\endgroup$– TimSep 22, 2020 at 8:38
-
$\begingroup$ Agree, but why revisiting vertices? I can wait there instead of revisiting the same vertex. $\endgroup$– lchenSep 22, 2020 at 10:04
-
$\begingroup$ Then I don't understand what you mean by the path delay. $\endgroup$– TimSep 22, 2020 at 10:54
-
$\begingroup$ By path delay I mean that traversing each edge $e$ incurs a delay $d_e$. We impose another constraint such that when starting at time $t$, we need to arrive at $v_t$ by time $t+D$ with $D$ being a tolerable delay. $\endgroup$– lchenSep 22, 2020 at 11:43
Let $f(i,t,W)$ be the minimum cost of a path to the sink, starting from node $i$ at time $t$ with current maximum $W$. We want to compute $f(v_s,0,-\infty)$, and $f$ satisfies the recursion: $$ f(i,t,W)= \begin{cases} W &\text{if $i=v_t$} \\ \min\limits_{e=(i,j)\in E,\ t'\in [t,T]} f(j,t',\max(W,w_e(t')) &\text{if $i\not=v_t$} \end{cases} $$ As an approximation, you can discretize the time interval to a finite set for each $e\in E$, as well as the set of $W$ values.