# An FPTAS for Dynamic Multiobjective Shortest Path Problems
## 2 Multiobjective Shortest Path Problems
Let \(p\) be a \((u,v)\)-path with \(k\) arcs that starts at \(u\) with costs \(\tau\in\mathbb{R}_{\geq 0}^{d}\). Then the costs of any leading subpath \(p_{|l}\), \(l\in\{2,\ldots,k\}\), of \(p\) are recursively given by  
\[ \begin{split} c\Big{(}p_{|l},\tau\Big{)}&:=\partial _{a_{1}}(\tau)=\tau+c_{a_{1}}(\tau)\in\mathbb{R}_{\geq 0}^{d},\\ c\Big{(}p_{|l},\tau\Big{)}&:=\partial_{a_{l}} \Big{(}c\Big{(}p_{|l-1},\tau\Big{)}\Big{)}=c_{a_{l}}\Big{(}c\Big{(}p_{|l-1}, \tau\Big{)}\Big{)}+c\Big{(}p_{|l-1},\tau\Big{)}\in\mathbb{R}_{\geq 0}^{d}.\end{split}  \tag{2}\]  
Finally, using \(p=p_{|k}\), the \(d\)-dimensional costs of path \(p\) starting with cost \(\tau\) are denoted by \(c(p,\tau)\), or, if the starting state \(\tau\) is clear, by \(c(p)\). In the static case, the costs of \(p\) are \(c(p):=\sum_{j=1}^{k}c_{a_{j}}\), where \(a_{j}\) denotes the \(j\)th arc of \(p\). In Multiobjective Optimization, optimal feasible solutions are called efficient solutions (cf. [6]). The feasible solutions to any MOSP instance are paths and hence, we seek to find efficient \((s,v)\)-paths with initial costs \(\tau_{0}\in\mathbb{R}_{\geq 0}^{d}\) for every \(v\in V\). Efficiency is defined in terms of a (strict) partial order on \(\mathbb{R}_{\geq 0}^{d}\) (cf. [5]). For our exact Multiobjective Dijkstra algorithm discussed in Section 3, we will use the following notion of efficiency and dominance:  
Definition 2 (Dominance): Given two cost vectors \(x,y\in\mathbb{R}_{\geq 0}^{d}\), \(x\) is said to dominate \(y\)\((x\preceq_{D}y)\), if and only if \(x_{i}\leq y_{i}\) for all \(i\in\{1,\ldots d\}\). Moreover, \(x\) is called efficient, if there is no other cost vector \(x^{\prime}\in\mathbb{R}_{\geq 0}^{d}\) such that \(x^{\prime}\preceq_{D}x\). This definition carries over to the set of feasible paths in a natural way: given two \((s,v)\)-paths \(p\) and \(q\), \(p\) is said to \(\preceq_{D}\)-dominate \(q\)\((p\preceq_{D}q)\) if and only if \((p)\preceq_{D}c(q)\). An \((s,v)\)-path is called \(\preceq_{D}\) -efficient if it is not \(\preceq_{D}\) -dominated by any other \((s,v)\)-path. Note that the set of efficient cost vectors of a Dyn-MOSP instance \(\mathcal{I}\) is unique. However, for every such point in \(\mathbb{R}_{\geq 0}^{d}\), there might be multiple efficient paths. The maximum complete set of efficient paths is the set that contains all paths whose cost vector is efficient, i.e., the set may contain paths with identical costs. If the widely used strict partial Pareto order is used to define dominance, the output of a Dyn-MOSP instance would be the maximum complete set. This order is the same as the one in Definition 2 but enforces that at least one of the inequalities is strict, hence not allowing \(x\) to dominate \(y\) if \(x=y\). In this paper we compute the minimum complete set of efficient paths that is induced by \(\preceq_{D}\) and allows exactly one efficient path per efficient cost vector. Example 1: _Figures 1 and 2 show an example of a biobjective Dyn-MOSP instance and how the costs of two paths evolve through the corresponding graph. We assume that at the nodes \(u\) and \(v\) there are paths (red and green) ending with costs \(\tau=(\tau_{1},\tau_{2})\) and \(\tau^{\prime}=(\tau_{1}^{\prime},\tau_{2}^{\prime})\), respectively, and that these paths are now extended towards node \(x\) via node \(w\). The plots to the left and in the middle show the costs for traversing the corresponding arc starting with costs \(\tau\) and \(\tau^{\prime}\), respectively. After the extension along the arcs \((u,w)\) and \((v,w)\) both paths meet at node \(w\) with costs \(\tau_{w}=\partial_{a_{1}}(\tau)\) and \(\tau_{w}^{\prime}=\partial_{a_{2}}(\tau^{\prime})\). The plots on the right show the arc cost functions corresponding to the arc \(a_{3}=(w,x)\). Furthermore, on the same diagram, the dominance relationship between both paths at \(w\) becomes clear since \(\tau^{\prime}_{w,1}<\tau_{w,1}\) and \(\tau^{\prime}_{w,2}>\tau_{w,2}\). This means that none of the paths ending at \(w\) dominates the other one._