Minimum spanning tree interdiction problem considering follower strategy stability

Authors
Javad Tayyebi
Malihe Niksirat
Birjand University of Technology
Abstract
Introduction: This paper examines a combinatorial optimization interdiction problem, called minimum spanning tree interdiction. From the point of view of game theory, this problem involves two players with different goals. The first player, called the follower, seeks to find a minimum spanning tree. On the other hand, the other player, who is called the leader, increases the cost of arcs, taking into account the budget and the bound constraints, which will make the value of the follower's objective function worse as much as possible, with the hope that the follower will stop doing more. In this article, a special case of the problem is considered in which the initial optimal tree remains optimal even with the change of weights. This assumption guarantees that the leader can be sure that the follower has no motivation to change his strategy, because a better strategy is not available.

Material and Methods: In order to efficiently solve this problem with linear costs, a new model is proposed, which includes a large number of constraints. For this reason, a solution approach based on the row (constraint) generation method is proposed for the problem. Then a numerical example and calculation results on random samples are presented to evaluate the performance of this method.

Results and discussion: The proposed model addresses this problem by utilizing a row generation approach to enhance solving efficiency. Computational results demonstrate its acceptable performance under various conditions, highlighting its potential for practical applications. The computational results indicate that the proposed algorithm computes the optimal solution to the problem within a finite number of iterations and a reasonable execution time.
Keywords
Minimum spanning tree
Interdiction problem
Fixed strategy
Linear cost function
[1] Abdelmaguid, T. F. (2018). An efficient mixed integer linear programming model for the minimum spanning tree problem. Mathematics, 6(4), 183.

[2] Abdolahzadeh, A., Aman, M., & Tayyebi, J. (2023). Bottleneck spanning tree interdiction problem with fixed and linear costs. Bulletin of the Transilvania University of Brasov. Series III: Mathematics and Computer Science, 185-198.

[3] Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network flows: Theory, applications and algorithms. Englewood Cliffs, New Jersey, USA: Prentice-Hall.

[4] Bazgan, C., Toubaline, S., & Vanderpooten, D. (2012). Efficient determination of the k most vital edges for the minimum spanning tree problem. Computers & Operations Research, 39(12), 2888-2898.

[5] Bazgan, C., Toubaline, S., & Vanderpooten, D. (2013). Critical edges/nodes for the minimum spanning tree problem: Complexity and approximation. Journal of Combinatorial Optimization, 26(2), 178-189.

[6] Frederickson, G. N., & Solis-Oba, R. (1999). Increasing the weight of minimum spanning trees. Journal of Algorithms, 33(2), 244-266.

[7] Ghorbani-Renani, N., González, A. D., & Barker, K. (2021). A decomposition approach for solving tri-level defender-attacker-defender problems. Computers & Industrial Engineering, 153, 107085.

[8] Johnson, M. P., Gutfraind, A., & Ahmadizadeh, K. (2014). Evader interdiction: Algorithms, complexity and collateral damage. Annals of Operations Research, 222(1), 341-359.

[9] Liang, W., & Shen, X. (1997). Finding the k most vital edges in the minimum spanning tree problem. Parallel Computing, 23(2), 1889-1907.

[10] Linhares, A., & Swamy, C. (2017). Improved algorithms for MST and metric-TSP interdiction. arXiv preprint arXiv:1706.00034.

[11] Liu, A. (2018). Graph Theory. In: S.M.A.R.T. Circle Minicourses. Springer Texts in Education. Springer, Cham.

[12] Mary, F. R. P., Mohanaselvi, S., & Broumi, S. (2023). A solution approach to minimum spanning tree problem under Fermatean fuzzy environment. Bulletin of Electrical Engineering and Informatics, 12(3), 1738-1746.

[13] Salazar-Zendeja, L. (2022). Models and algorithms for the minimum spanning tree interdiction problem (Doctoral dissertation). Centrale Lille Institut.

[14] Sepasian, A. R., & Monabbati, E. (2017). Upgrading min–max spanning tree problem under various cost functions. Theoretical Computer Science, 704, 87-91.

[15] Smith, J. C., & Song, Y. (2020). A survey of network interdiction models and algorithms. European Journal of Operational Research, 283(3), 797-811.

[16] Tayyebi, J., Mitra, A., & Sefair, J. A. (2023). The continuous maximum capacity path interdiction problem. European Journal of Operational Research, 305(1), 38-52.

[17] Wei, N., Walteros, J. L., & Pajouh, F. M. (2021). Integer programming formulations for minimum spanning tree interdiction. INFORMS Journal on Computing, 33(4), 1461-1480.

[18] Zenklusen, R. (2015, October). An O(1)-approximation for minimum spanning tree interdiction. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (pp. 709-728). IEEE.