Optimal cost augmentation and interdiction problem for the Minimum Spanning Tree

This paper examines the Minimum Spanning Tree Interdiction (MSTI) problem, a two-player game between a network operator and an interdictor. The network operator seeks to construct a Minimum Spanning Tree (MST) in a given network, while the interdictor aims to disrupt this process by altering the network topology within a limited budget, thereby maximizing the weight of the resulting MST. Two types of interdiction are considered: total interdiction, where an interdicted edge is removed entirely from the network, and partial interdiction, where the weight of an interdicted edge is augmented by a predefined amount. The interdictor’s budget is modeled either as a cardinality constraint, where all edges have the same interdiction cost, or as a knapsack constraint, where interdiction costs vary across edges. To address a generalized version of the MSTI problem, we propose four mathematical formulations and develop valid inequalities to strengthen one of the models. An analysis of the relations among the models is performed to determine the dominance between them. Finally, computational experiments are conducted to demonstrate the effectiveness and efficiency of the proposed formulations.