Minimum-Cost Shortest-Path Interdiction Problem Involving Upgrading Edges on Trees with Weighted l ∞ Norm

Network interdiction problems involving edge deletion on shortest paths have wide applications. However, in many practical scenarios, the complete removal of edges is infeasible. The minimum-cost shortest-path interdiction problem for trees with the weighted l ∞ norm (MCSPIT ∞ ) is studied in this paper. The goal is to upgrade selected edges at minimum total cost such that the shortest root–leaf distance is bounded below by a given value. We designed an O ( n log n ) algorithm based on greedy techniques combined with a binary search method to solve this problem efficiently. We then extended the framework to the minimum-cost shortest-path double interdiction problem for trees with the weighted l ∞ norm, which imposes an additional requirement that the sum of root–leaf distances exceed a given threshold. Building upon the solution to (MCSPIT ∞ ), we developed an equally efficient O ( n log n ) algorithm for this variant. Finally, numerical experiments are presented to demonstrate both the effectiveness and practical performance of the proposed algorithms.