# An FPTAS for Dynamic Multiobjective Shortest Path Problems
## 2 Multiobjective Shortest Path Problems  
We start this section with a combinatorial definition of the Dyn-MOSP problem. Its components will be explained immediately afterwards. **Definition 1** (Dynamic Multiobjective Shortest Path Problem). : _Given a directed graph \(G=(V,A)\), a start node \(s\in V\), an initial cost vector \(\tau_{0}\in\mathbb{R}_{\geq 0}^{d}\), a dimension \(d\in\mathbb{N}\), and an arc cost function \(c:A\to\mathbb{F}^{d}\) (see Equation (1)), the \(d\) dimensional Dynamic Multiobjective Shortest Path Problem is to find either a minimum or a maximum complete set of efficient \((s,v)\)-paths in \(G\) for all \(v\in V\) (which type of set is output depends on the partial order used to define the minimality of paths)._  
Graph terminology  
We refer to the end-nodes of an arc \(a\in A\) as the tail and the head nodes of \(a\). Given two nodes \(u\), \(v\in V\), a \((u,v)\)-path in \(G\) is a sequence \((a_{1},\ldots,a_{k})\), \(k\in\mathbb{N}\), of arcs such that \(u\) is the tail node of \(a_{1}\) and \(v\) is the head node of \(a_{k}\). Additionally, the head node of \(a_{i}\) coincides with the tail node of \(a_{i+1}\) for any \(i\in\{1,\ldots,k-1\}\). We denote by \(p_{\mid l}\) for any \(l\in\{1,\ldots,k\}\) the leading subpath of \(p\) consisting of the first \(l\) arcs of \(p\). The arc cost function \(c\)  
In a \(d\)-dimensional Dyn-MOSP instance \(\mathcal{I}\), each arc \(a\in A\) bears \(d\) independent real valued cost functions \(c_{a,i}:\mathbb{R}_{\geq 0}\to\mathbb{R}_{\geq 0}\), \(i\in\{1,\ldots,d\}\); these will be used to propagate costs along the paths. The propagation can be described conveniently in terms of cost propagation functions \(\xi_{a,i}:=id+c_{a,i}:\mathbb{R}_{\geq 0}\to\mathbb{R}_{\geq 0}\), \(i\in\{1,\ldots,d\}\). Then, given a cost vector \(\tau\in\mathbb{R}_{\geq 0}^{d}\), its cost component \(\tau_{i}\) is propagated along arc \(a\) to become \(\dot{c}_{a,i}(\tau_{i}):=\tau_{i}+c_{a,i}(\tau_{i}),i\in\{1,\ldots,d\}\), and along path \(p=(a_{1},\ldots,a_{k})\) to become \(c_{i}(p,\tau_{i})=\dot{c}_{a_{k,i}}(\dot{c}_{a_{k,i}(\tau_{i})}(\dot{c}_{a_{k,i}(\tau_{i})}))\), \(i\in\{1,\ldots,d\}\). Throughout this paper, we will consider paths starting at a source node \(s\) with arbitrary, but fixed, starting costs \(\tau_{0,i}\), \(i\in\{1,\ldots,d\}\); for such paths let us omit the starting costs \(\tau_{0,i}\) from the notation and abbreviate \(c_{i}(p,\tau_{0,i})\) by \(c_{i}(p)\). Arc costs of this type arise in applications where multidimensional \"state flows\" evolve through a graph. For example, in the Flight Planning problem that we will discuss in Section 5.1, the costs \(\tau_{v}\) at a node \(v\) of a path \(p\) are interpreted as the aircraft state, i.e., a tuple consisting of the flight time, the fuel consumption, the distance etc. from the source node until \(v\), and \(\dot{c}_{v,w}(\tau_{0})=\tau_{v}+c_{(v,w)}(\tau_{v})\) are the costs (in this example, the aircraft state) at the successor node \(w\) of \(v\) in \(p\). We use \(\tau\) to denote the costs because one of the costs is typically time. Note also that in the static case, the arc cost functions are constant and hence, we can write \(c_{a,i}\) instead of \(c_{a,i}(\tau)\). If we denote by \(\mathbb{F}\) the set of functions from \(\mathbb{R}_{\geq 0}\) to \(\mathbb{R}_{\geq 0}\), we can denote the arc cost function \(c\) and the arc cost propagation function \(\partial\) of \(\mathcal{I}\) in vector and function notation by  
\[ \begin{split} c:A&\to\mathbb{F}^{d}\qquad\qquad \partial:A\to\mathbb{F}^{d}\\ a&\mapsto c_{a}:=[c_{a,i}]_{i=1}^{d}.\quad\quad a \mapsto\partial_{a}:=[id+c_{a,i}]_{i=1}^{d}.\end{split}  \tag{1}\]  
Then, given a cost vector \(\tau\in\mathbb{R}_{\geq 0}^{d}\), the costs for traversing an arc \(a\) starting with costs \(\tau\) at \(a\)'s tail node are \(c_{a}(\tau):=[c_{a,i}(\tau_{i})]_{i=1}^{d}\in\mathbb{R}_{\geq 0}^{d}\), and costs \(\tau\) are propagated along arc \(a\) to become \(\partial_{a}(\tau)=[\tau_{i}+c_{a,i}(\tau)]_{i=1}^{d}\in\mathbb{R}_{\geq 0}^{d}\).