## 3 System Model and Problem Formulation
### Problem Formulation  
Our objective is to determine a task offloading scheme \(x\) that minimizes the total delay while satisfying the cost constraint, considering a network with task dependencies and service caching.  
\[C(j,x)=C_{j}^{x_{j}}+\sum_{i\in\mathcal{C}(j)}\left[C(i,x)+C_{ij}^{x_{i}x_{j} }\right]. \tag{3}\]  
\(C(j,x)\) represents the cost of completing task \(j\) in offloading scheme \(x\). \(x_{j}\) denotes the device selected for offloading task \(j\). The set \(C(j)\) represents the set of predecessor nodes of node \(j\). \(C_{j}^{x_{j}}\) represents the processing cost incurred by server \(x_{j}\) for handling task \(j\). Additionally, \(C_{ij}^{x_{i}x_{j}}\) denotes the communication cost between server \(x_{i}\), which offloads task \(i\), and server \(x_{j}\), which offloads task \(j\). As described in the above equation, the total cost of completing task \(j\) is the sum of the costs of completing all its predecessor tasks, the data transmission cost, and the execution cost of task \(j\).  
\[T(j,x)=\max_{i\in\mathcal{C}(j)}\left[T(i,x)+T_{ij}^{x_{i}x_{j}}\right]+T_{j}^ {x_{j}}. \tag{4}\]  
\(T(j,x)\) represents the time required to complete task \(j\) in offloading scheme \(x\). \(T_{j}^{x_{j}}\) represents the processing delay incurred by server \(x_{j}\) for handling task \(j\). Additionally, \(T_{ij}^{x_{i}x_{j}}\) denotes the communication delay between server \(x_{i}\), which offloads task \(i\), and server \(x_{j}\), which offloads task \(j\). Task \(i\) can only be executed after data has been transmitted from all its predecessor nodes, and its execution time is determined by the slowest predecessor node.  
\(P\): \(\min_{x\in[M_{0}]^{V}}T(V,x)\)  
s.t. \(C(N^{\prime},x)\leq T\),  
\(|x_{i}|-|x_{j}|\geq 0\), \(\forall x_{i},x_{j}\in x\), \(\forall(i,j)\in E\)  
Figure 2: An example of an offloading scheme that considers both service caching and task dependency.  
In this context, \(C(N^{\prime},x)\) and \(T(V,x)\) are defined in (3) and (4), respectively. Here, \(M_{v}=\{m_{1},m_{2},\ldots,m_{M^{\prime}}\}\) denote the set of execution nodes that satisfy the service cache requirements for task \(v\), \(V\) represents the set of all tasks, \(N^{\prime}\) denotes the last task in the sequence, and \(T\) represents the cost constraint. The first constraint indicates that the cost incurred when completing the virtual task \(t\) should not exceed the cost limit. The second constraint ensures that the successor tasks can only be offloaded once the predecessor tasks have been completed.  
**Theorem 1**: \(P\) _is NP-hard._  
In a serial task graph where service caching and data transmission are not considered, we transform the binary partition problem of \(P\) into a 0-1 knapsack problem. Since the 0-1 knapsack problem is NP-hard, problem \(P\) is at least NP-hard as well [32].  
We rewrite a special case of the original problem \(P\) as problem \(P^{\prime}\), where \(C_{i}^{0}=0\). \(C_{i}^{1}\) and \(T_{i}^{1}\) represent the cost and delay required to complete task \(i\), respectively.  
\[P^{\prime}:\ \min_{x_{i}\in\{0,1\}}\sum_{i=1}^{N^{\prime}}\Bigl{[}(1-x_{ i})T_{i}^{0}+x_{i}T_{i}^{1}\Bigr{]}\] \[\text{s.t.}\ \sum_{i=1}^{N^{\prime}}x_{i}C_{i}^{1}\leq T\]  
By setting \(T_{i}^{0}=0\), \(T_{i}^{1}=-v_{i}\), and \(C_{i}^{1}=w_{i}\) problem \(P^{\prime}\) can be transformed into problem \(Q\), which corresponds to the 0-1 knapsack problem.  
\[Q:\ \max_{x_{i}\in\{0,1\}}\sum_{i=1}^{N^{\prime}}x_{i}v_{i}\] \[\text{s.t.}\ \sum_{i=1}^{N^{\prime}}x_{i}w_{i}\leq T\]  
If we solve \(P^{\prime}\), we can also solve \(Q\). Since \(P^{\prime}\), as a special case of the original problem \(P\), is NP-hard, it follows that the original problem \(P\) is also NP-hard.