## 1 Introduction
Considering service caching leverages the user-proximity feature of MEC to meet the high-bandwidth, high-data-rate, and low-latency requirements of 6G, thereby promoting the convergence of communication, computation, and caching (3C) [16]. On the other hand, incorporating task dependency facilitates the integration of AI technologies, such as object and pose recognition applications, with MEC, further enhancing the role and applicability of MEC in the 6G era [17]. Although many current studies take both factors into account, their approaches are either based on deep learning or solved through heuristic algorithms [10; 19; 30; 31], which cannot guarantee that the offloading strategy obtained is the optimal solution or close to the optimal solution, and they lack strong performance guarantees. To overcome these constraints, effectively solve the offloading problem, and ensure the optimality of the offloading schemes, we propose both a polynomial-time approximation algorithm and an exact algorithm. These algorithms are improved based on dynamic programming (DP) and the Bellman-Ford algorithm, respectively. We summarize the main contributions as follows. * We define the delay-minimization problem under task dependency, service caching, and the maximum completion cost constraint, and prove its NP-hardness. Due to dependency, the delay and cost of task offloading are related to all the predecessor nodes. However, many existing studies fail to take this into account, which is of practical importance for delay-sensitive applications. * We then propose a \((1+\epsilon)\)-approximation algorithm to solve the aforementioned problem, and derive its time complexity as \(O(d_{in}N^{\prime}M^{\prime}{}^{2}\frac{L}{\epsilon}(\log\log(UB/LB)+1))\), where \(L\) denotes the depth of the task graph, \(d_{in}\) denotes the maximum indegree of the task graph, \(M^{\prime}\) is the number of execution devices, \(N^{\prime}\) is the number of tasks, and \(LB\) and \(UB\) represent the lower and upper bounds of the delay, respectively. In this paper, our approximation algorithm enables each task to make its offloading decision based on local information during execution, without the need to consider global decisions. Moreover, it provides worst-case performance guarantees, which aligns well with the characteristics of the distributed structure of MEC. * We propose an exact algorithm that can obtain the optimal solution to the aforementioned problem. Although its time complexity is theoretically exponential, in practice, the running time is much smaller than the theoretical value when solving real-world problems. * We finally evaluate the proposed algorithm using a random task model and a real task model, then compare it with the FixDoc algorithm [19], the Hermes algorithm [32], and a brute force algorithm. The simulation results validate the approximation ratio \((1+\epsilon)\) and the superiority of the obtained offloading scheme of our algorithm over the other algorithms. The rest of this paper is organized as follows. Section 2 summarizes the related work. In Section 3, we model the problem and prove its complexity. Section 4 presents the polynomial-time approximation algorithm. Section 5 introduces the exact algorithm. In Section 6, we conduct experiments and discuss the proposed algorithms. Finally, Section 7 concludes the paper.