BOTTLENECK SPANNING TREE INTERDICTION PROBLEM WITH FIXED AND LINEAR COSTS

Abstract

This paper investigates a combinatorial optimization interdiction problem, called bottleneck spanning tree interdiction. This problem is a game containing two players with conflicting goals. The first player, called the user, wants to find a bottleneck (min-max or max-min) spanning tree in a weighted network. The other player, called the attacker, increases edge weights under a budget constraint as well as bound constraints so that the user does not achieve his/her goal. This game has a hierarchy structure. It means that the attacker first perturbates the network and then, the user chooses his/her strategy after observing the attacker’s action. This paper considers the problem in two cases that there are fixed and linear costs for the attacker. Two divide-and-conquer algorithms are developed to solve the problem under both the costs in polynomial time.