# An FPTAS for Dynamic Multiobjective Shortest Path Problems
## 3 The Multiobjective Dijkstra Algorithm for Dynamic MOSP Problems
### Description of the Algorithm
In the context of MOSP problems, it states that an efficient \((s,v)\)-path contains only efficient subpaths. Given that the arc cost functions are FIFO, [PERSON]'s principle holds for efficient paths of the Dyn-MOSP problem. In particular, the following statement holds. **Lemma 1**. : _Given a Dyn-MOSP instance with FIFO arc cost functions, consider two \((s,v)\)-paths \(p\), \(p^{\prime}\) such that \(c(p)\preceq_{D}c(p^{\prime})\). Then, for the extensions of \(p\) and \(p^{\prime}\) along a \((v,w)\)-path \(q\) in \(G\) there holds \(c(p\circ q)\preceq_{D}c(p^{\prime}\circ q)\)._Proof. : Since \(c(p)\preceq_{D}c(p^{\prime})\), we know that \(c_{j}(p)\leq c_{j}(p^{\prime})\) for any \(j\in\{1,\ldots,d\}\). Due to the FIFO property of the arc cost functions, this implies that after \(q\)'s first arc, say \(a\in A\), there holds

\[c(p\circ a)=\hat{c}_{a}(c(p))\leq\hat{c}_{a}(c(p^{\prime}))=c(p^{\prime}\circ a).\]

This argument can be repeated along every arc of \(q\) until we reach the paths' end point, implying that \(c(p\circ q)\preceq_{D}c(p^{\prime}\circ q)\). The consequence of Lemma 1 is that during Algorithm 1, dominated labels/paths can be neglected since they will not become efficient later on. Hence, for a Dyn-MOSP instance whose arc cost function has the FIFO property in every dimension, Algorithm 1 computes a minimal complete set of efficient paths. The rest of the correctness proof proceeds along standard lines as in the static case (cf. [16; 17]). ### Complexity

The running time of Algorithm 1 is dominated by the running time of nextCandidateLabel and propagate, that both depend on the complexity of the oracle BLACK_BOX_DOM. It implements the dominance checks that are applied in the different versions of the MD-A that we discuss throughout the paper. In the exact biobjective algorithm, the dominance check (see Algorithm 2) can be implemented in constant time. The reason is that the sets \(L_{v}\) are sorted in lexicographically increasing order and contain only efficient labels. Indeed, the first cost component is sorted in increasing order, while the second cost component is sorted in decreasing order. Thus, a new tentative label that is lexicographically greater than all elements of \(L_{v}\) must only be compared with the last element. This observation seems to be not very widespread in the literature, but given the possibly exponential number of efficient paths at any node, the possibility of checking dominance in constant time has a big impact in theory and practice (cf. [16; 17; 23]). For \(d\geq 3\) the complexity is linear in the number of labels contained in \(L_{v}\), since in the worst case, the tentative label has to be compared with all existing ones (see Algorithm 3). In our analysis, we will denote the complexity of the dominance check, i.e., of the function BLACK_BOX_DOM, by \(\mathcal{C}\). We assume that \(Q\) is a Fibonacci-Heap [24] to get constant time complexity for the update and the insertion of labels. The label extraction is performed in \(\mathcal{O}(\log n)\), since the size of \(Q\) is at most \(n\). We set \(\mathcal{N}_{\max}:=\max_{v\in V}|L_{v}|\) to be the maximal number of labels at a single node at the end of the algorithm. \(\mathcal{N}:=\sum_{v\in V}|L_{v}|\) is the total number of computed efficient labels. **Remark 1**. : _Note that we assume that the evaluation of the arc cost functions can be done in constant time. This is for example the case, when the functions are piecewise linear/constant and the breakpoints are distributed equidistantly. This assumption is common in the literature on Time-Dependent Shortest Paths problems. However, note that logarithmic running times have to be assumed if the breakpoints are spaced without regularity (binary search to find the neighboring breakpoints), or even worse complexities if the functions cannot be easily parametrized.