A Shortest Path Interdiction Problem By Upgrading Critical Edges Under Hamming Distance On Trees

There are two main types of classical network interdiction problems by deleting critical edges.The first is K-most-vital-edge problem which aims to delete at most K edges of the network to make some network performances worse than before.For example,maximize the shortest path between a pair of nodes.The second is the vital edge interdiction problem which aims to delete some critical edges as few as possible to make some network performance satisfy some given bounds.For instance,make the length of the shortest path is upper bounded by some constant value.Network interdiction problem by deleting critical edges has wide applications in transportation network,communication network,war network,terrorist network and drug trafficking networks etc.However,in some practical applications,deleting edges can not be permitted.According to the example in network war,we put forward a concept of updating critical edges and focus on the shortest path interdiction problem(denoted by SPIP)by updating critical edges under Hamming distance on trees.The objective is to upgrade the edge lengths to maximize the distance under some measurement from the root to all the leaves while the cost incurred by upgrading is upper bounded by a given value K.The distance from the root to all the leaves on trees can be defined in two ways based on practical application.The first is the minimum of the lengths for the paths from the root to all the leaves.The second is the sum of the lengths for the paths from the root to all the leaves.And the two corresponding SPIPs are the SPIP to maximize the minimum path length by upgrading critical edges under Hamming distance on trees(denoted by(SPIP-MMPL-UCEH-T))and the SPIP to maximize the sum of path lengths by upgrading critical edges under Hamming distance on trees(denoted by(SPIP-MSPL-UCEH-T)),respectively.We consider two cases based on the unit weight vector c>0 and c=1 incurred by updating edges.To the latter case,two cases depending on the number of critical edges K= 1 and K>1 are considered.We construct the models of problems,design optimization algorithms,prove the optimality and analyze the time complexities.For the problem(SPIP-MMPL-UCEH-T),when the unit weight vector c>0,we first show that the problem defined on chains can be transformed into a 0-1 knapsack problem and hence is NP-hard.Then we extend the NP-hardness onto the chain trees and general trees.When the unit weight vector c=1,we first provide a greedy algorithm with time complexity O(m+l log l)when K=1;then propose a dynamic programming algorithm with time complexity O(min{m,l2}(m+K2)+l2K3)when K>1 using a subtree structure,where m and l are the numbers of edges and leaves in a given tree,respectively.For the problem(SPIP-MSPL-UCEH-T),when the unit weight vector c>0,we show that this problem is NP-hard by transforming it into 0-1 knapsack problem model.When c=1,we propose two greedy algorithms with the same time complexities O(m)for the cases K=1 and K>1.At last,we also consider the SPIP to maximize the sum of path lengths by upgrading critical edges under l1 norm on trees.By transforming the model into a continuous knapsack problem,we prove the problem can be solved in O(m)time.