# An FPTAS for Dynamic Multiobjective Shortest Path Problems
## 3 The Multiobjective Dijkstra Algorithm for Dynamic MOSP Problems
### Description of the Algorithm
The \(k^{th}\) iteration proceeds with a call to nextCandidateLabel, where at least one permanent label per predecessor node of \(v\) is considered. Since the current iteration is the first time that nextCandidateLabel is called for \(v\) since \(l_{u}\)'s insertion, lastProcessedLabel\((u,v)\) points at a label in \(L_{u}^{k}\) that is not after \(l_{u}\). We want to prove an upper bound on the number of times that \(\ell_{v}\) is considered, so we assume w.l.o.g. that \(\ell_{u}\) is considered during the current search for \(v\)'s new label in \(Q\), i.e., lastProcessedLabel\((u,v)\) advances at least until \(\ell_{u}\)'s position in \(L_{u}^{k}\). Hence, \(\ell_{u}\) is extended along the arc \((u,v)\), generating \(\ell_{v}\) as a candidate to enter \(Q\) in iteration \(k\). According to Line 8 in nextCandidateLabel, lastProcessedLabel\((u,v)\) is increased if there is a label in \(L_{v}^{k}\) that (\(\operatorname{pos}\)-)dominates \(\ell_{v}\). If this happens, later searches for a new tentative label for \(v\) no longer consider \(\ell_{u}\) as a possible predecessor label and hence, ignore \(\ell_{v}\). In case \(L_{v}^{k}\
subseteq L_{v}\)\(\ell_{v}\), lastProcessedLabel\((u,v)\) will not be altered and the next search for a new tentative label for \(v\) will consider \(\ell_{v}\) again. Since such searches only happen when a label for \(v\) is made permanent, \(\ell_{v}\) will be considered at most \(|L_{v}|\) times during calls to nextCandidateLabel. The following theorem proves the correctness of the MD-FPTAS for the static case. Its proof is similar to the one given in [3]. Recall that efficient paths can have at most \(n-1\) arcs since the arc cost functions are positive. Figure 3: Three consecutive iterations of the MD-FPTAS. The extracted label \(\ell^{*}\) in every iteration is marked in red, the permanent labels \(\ell\in L_{v}\) in black, and the tentative labels generated in nextCandidateLabel or propagate in grey. **Theorem 1**. : _Consider a node \(v\in V\) and an efficient \((s,v)\)-path \(p^{*}=(a_{1},\ldots,a_{k})\). Then, the MD-FPTAS finds an \((s,v)\)-path \(\tilde{p}\) s.t._

\[c(\tilde{p})\leq r^{k}c(p^{*}).\]

Proof. : We prove the statement by induction over \(k\), the number of arcs of \(p^{*}\). W.l.o.g. we assume that no parallel arcs exist in \(G\). In the base case, we consider an efficient single-arc path \(p^{*}=((s,v))\). In the first iteration of Algorithm 1, the label \(\ell^{*}\) corresponding to \(p^{*}\) will be added to \(Q\) during propagate. Consider the first iteration in which a label \(\ell\) for node \(v\) is extracted from \(Q\). If \(\ell=\ell^{*}\), we are done since \(\ell^{*}\) itself is made permanent. In case \(\ell\
eq\ell^{*}\), Lemma 2 implies that \(\ell^{*}\) will be made permanent later or be discarded. If it is discarded, Algorithms 4 and 5 guarantee the existence of a permanent label \(\tilde{\ell}\in L_{v}\) corresponding to an \((s,v)\)-path \(\tilde{p}\) such that

\[c_{1}(\tilde{p})\leq c_{1}(p^{*})\] (6a) and \[\text{pos}(\tilde{p})\leq\text{pos}(p^{*}). \tag{6b}\]

For \(j\in\{2,\ldots,d\}\), we can derive \(\log_{r}(c_{j}(\tilde{p}))-1\leq\log_{r}(c_{j}(p^{*}))\) from (6b) and this in turn can be restated as \(c_{j}(\tilde{p})\leq rc_{j}(p^{*})\), which, coupled with (6a), proves the statement. In the induction hypothesis, we assume that

\[c(\tilde{p})\leq r^{k-1}c(p^{*}), \tag{7}\]

holds for any \(k\in\{2,\ldots n-1\}\) and efficient paths \(p^{*}\) with \(k-1\) arcs. Induction Step: Let \(p^{*}\) be an efficient \((s,v)\)-path with \(k\) arcs and let \((u,v)\) be its last arc. Due to subpath efficiency, the \((s,u)\)-subpath \(p^{*}_{u}\) of \(p^{*}\) is efficient. In addition, the induction hypothesis guarantees the existence of a path \(\tilde{p}_{u}\) with corresponding permanent label \(\tilde{\ell}_{u}\) such that (7) holds for \(\tilde{p}_{u}\) and \(p^{*}_{u}\). When \(\tilde{\ell}_{u}\) is extracted and made permanent, the label \(\tilde{\ell}:=(v,c_{\tilde{\ell}_{u}}+c_{(u,v)},\tilde{\ell}_{u})\) is analyzed in propagate.