0
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ One way is to define Ricci flow on Graphs by the Olliver-Ricci curvature and the Forman-Ricci curvature $\endgroup$
    – user160903
    Sep 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$
    – lchen
    Sep 17, 2020 at 1:34
  • $\begingroup$ Should the summand $c_e(t_e)$ instead be $w_e(t_e^P)$? $\endgroup$
    – RobPratt
    Sep 20, 2020 at 13:47
  • $\begingroup$ @RobPratt Thank you for pointing out. I have corrected the typo. $\endgroup$
    – lchen
    Sep 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$
    – RobPratt
    Sep 20, 2020 at 14:17

2 Answers 2

1
+50
$\begingroup$

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.

$\endgroup$
18
  • $\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$
    – lchen
    Sep 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$
    – Tim
    Sep 22, 2020 at 8:38
  • $\begingroup$ Agree, but why revisiting vertices? I can wait there instead of revisiting the same vertex. $\endgroup$
    – lchen
    Sep 22, 2020 at 10:04
  • $\begingroup$ Then I don't understand what you mean by the path delay. $\endgroup$
    – Tim
    Sep 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$
    – lchen
    Sep 22, 2020 at 11:43
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.