Dynamic Maximum Capacity Path Interdiction with Asymmetric Information: Strongly Polynomial-Time Algorithms

Articles in Press

Document Type : Original paper

Authors

1 Department of Mathematics, Faculty of Science, University of Birjand, Iran

2 Department of Industrial Engineering, Faculty of Industrial and Computer Engineering, Birjand University of Technology, Birjand, Iran

Abstract

This paper introduces a novel non-cooperative game played on a capacitated network involving a defender and an attacker. The attacker seeks to maximize the capacity of a path from an origin to a destination, but operates under the constraint of limited network visibility, necessitating a greedy path selection strategy. Conversely, the fully informed defender aims to thwart the attacker's objective by strategically reducing arc capacities within a budgetary constraint. The game unfolds in multiple rounds, with the defender making capacity reduction decisions followed by the attacker's local path extension. This dynamic setting with asymmetric information characterizes the problem as the dynamic maximum capacity path interdiction problem. We present a strongly polynomial algorithm to solve this challenging game. Subsequently, an enhanced algorithm is developed to significantly improve computational efficiency. Extensive computational experiments validate the efficacy of both algorithms, demonstrating that the latter achieves approximately half the runtime of the former.

Keywords

Main Subjects

References

[1] A. Abdolahzadeh, M. Aman, and J. Tayyebi, Minimum st-cut interdiction problem, Computers and Industrial Engineering 148 (2020), 106708. https://doi.org/10.1016/j.cie.2020.106708
[2] A. Abdolahzadeh, M. Aman, and J. Tayyebi, Bottleneck spanning tree interdiction problem with fixed and linear costs,
Bulletin of the Transilvania University of Brasov. Series III: Mathematics and Computer Science 3 (2023), no. 1, 185–198.
https://doi.org/10.31926/but.mif.2023.3.65.1.14
[3] R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, Network Flows: Theory, Applications and Algorithms, Prentice-Hall, Englewood Cliffs, New Jersey, USA, 1993.
[4] İ. Akgün, B.Ç. Tansel, and R.K. Wood, The multi-terminal maximum-flow network-interdiction problem, Eur. J. Oper. Res. 211 (2011), no. 2, 241–251. https://doi.org/10.1016/j.ejor.2010.12.011
[5] U. Anjarassuk and J. Linderoth, Reformulation and sampling to solve a stochastic network interdiction problem, Networks 52 (2008), no. 3, 120–132. https://doi.org/10.1002/net.20237
[6] N. Assimakopoulos, A network interdiction model for hospital infection control, Computers in Biology and Medicine 17 (1987), no. 6, 413–422. https://doi.org/10.1016/0010-4825(87)90060-6
[7] E. Azizi and A. Seifi, Solution algorithms for shortest path network interdiction with symmetric and asymmetric information, Int. J. Sys. Sci.: Operations and Logistics 10 (2023), no. 1, 2247964. https://doi.org/10.1080/23302674.2023.2247964
[8] E. Azizi and A. Seifi, Shortest path network interdiction with incomplete information: a robust optimization approach, Ann. Oper. Res. 335 (2024), no. 2, 727–759. https://doi.org/10.1007/s10479-023-05350-1
[9] M. Backhaus and G. Schaefer, Towards the complexity of the widest path problem in hybrid multi-channel WMNs, 2020 16th International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob), IEEE, 2020, pp. 378–381.
[10] H. Bayrak and M.D. Bailey, Shortest path network interdiction with asymmetric information, Networks 52 (2008), no. 3, 133–140. https://doi.org/10.1002/net.20236
[11] H. Bigdeli, S.M.S. Mirdamadi, and J. Tayyebi, A meta-heuristic method for maximum capacity path interdiction problem with multiple attackers, Journal of Modeling in Engineering 20 (2022), no. 70, 133–146. https://doi.org/10.22075/jme.2022.26026.2213
[12] J.S. Borrero, O.A. Prokopyev, and D. Sauré, Sequential shortest path interdiction with incomplete information, Decis. Anal. 13 (2016), no. 1, 68–98. https://doi.org/10.1287/deca.2021.0426
[13] G. Brown, M. Carlyle, J. Salmerón, and K. Wood, Defending critical infrastructure, Interfaces 36 (2006), no. 6, 530–544.
https://doi.org/10.1287/inte.1060.0252
[14] K.J. Cormican, D.P. Morton, and R.K. Wood, Stochastic network interdiction, Oper. Res. 46 (1998), no. 2, 184–197.
https://doi.org/10.1287/opre.46.2.184
[15] S. Dong, K. Abbas, and R. Jain, A survey on distributed denial of service (DDoS) attacks in SDN and cloud computing environments, IEEE Access 7 (2019), 80813–80828. https://doi.org/10.1109/ACCESS.2019.2922196
[16] P. Erdös and A. Rényi, On the evolution of random graphs, Selected Papers of Alfréd Rényi 2 (1976), 482–525.
[17] F. Fang, S. Liu, A. Basak, Q. Zhu, C.D. Kiekintveld, and C.A. Kamhoua, Introduction to game theory, Game Theory and Machine Learning for Cyber Security (2021), 21–46.
[18] R. Hemmecke, R. Schultz, and D.L. Woodruff, Interdicting stochastic networks with binary interdiction effort, Network interdiction and stochastic integer programming, vol. 22, Springer, Boston, MA, 2003, pp. 69–84. https://doi.org/10.1007/0-306-48109-X_4
[19] L. Hu and L. Zhang, Real-time internet traffic identification based on decision tree, World Automation Congress 2012, IEEE, June 2012, pp. 1–3.
[20] D. Huang, Z. Mao, K. Fang, and L. Chen, Solving the shortest path interdiction problem via reinforcement learning, International Journal of Production Research 61 (2023), no. 1, 31–48. https://doi.org/10.1080/00207543.2021.2002962
[21] K.T. Kennedy, R.F. Deckro, J.T. Moore, and K.M. Hopkinson, Nodal interdiction, Math. Comput. Modell 54 (2011), no. 11-12, 3116–3125. https://doi.org/10.1016/j.mcm.2011.07.041
[22] L. Khachiyan, E. Boros, K. Borys, K. Elbassioni, V. Gurvich, G. Rudolf, and J. Zhao, On short paths interdiction problems: Total and node-wise limited interdiction, Theory of Comput. Syst. 43 (2008), no. 2, 204–233. https://doi.org/10.1007/s00224-007-9025-6
[23] F. Ljunggren, K. Persson, A. Peterson, and C. Schmidt, Railway timetabling: a maximum bottleneck path algorithm for finding an additional train path, Public Transp. 13 (2021), no. 3, 597–623. https://doi.org/10.1007/s12469-020-00253-x
[24] B.J. Lunday and H.D. Sherali, A dynamic network interdiction problem, Informatica 21 (2010), no. 4, 553–574.
https://doi.org/10.15388/Informatica.2010.305
[25] M. Mahmoodjanloo, S.P. Parvasi, and R. Ramezanian, A tri-level covering fortification model for facility protection against disturbance in r-interdiction median problem, Computers and Industrial Engineering 102 (2016), 219–232. https://doi.org/10.1016/j.cie.2016.11.004
[26] A. Mohammadi and J. Tayyebi, Maximum capacity path interdiction problem with fixed costs, Asia-Pac. J. Oper. Res. 36 (2019), no. 04, 1950018. https://doi.org/10.1142/S0217595919500180
[27] D.P. Morton, F. Pan, and K.J. Saeger, Models for nuclear smuggling interdiction, IIE Transactions 39 (2007), no. 1, 3–14.
https://doi.org/10.1080/07408170500488956
[28] H. Nguyen-Thu, J. Tayyebi, K.T. Nguyen, and N.T. Luan, The quickest root-leaf interdiction problem on tree networks, Discrete Appl. Math. 368 (2025), 91–104. https://doi.org/10.1016/j.dam.2025.02.020
[29] O. Osanaiye, K.K.R. Choo, and M. Dlodlo, Distributed denial of service (DDoS) resilience in cloud: Review and conceptual cloud DDoS mitigation framework, Journal of Network and Computer Applications 67 (2016), 147–165.
https://doi.org/10.1016/j.jnca.2016.01.001
[30] S.I.Z. Punla-Green, J.E. Mitchell, J.L. Gearhart, W.E. Hart, and C.A. Phillips, Shortest path network interdiction with asymmetric uncertainty, Networks 83 (2024), no. 3, 605–623. https://doi.org/10.1002/net.22208
[31] A.P. Punnen, A linear time algorithm for the maximum capacity path problem, European J. Oper. Res. 53 (1991), no. 3, 402–404. https://doi.org/10.1016/0377-2217(91)90073-5
[32] S. Sadeghi, A. Seifi, and E. Azizi, Trilevel shortest path network interdiction with partial fortification, Computers and Industrial Engineering 106 (2017), 400–411. https://doi.org/10.1016/j.cie.2017.02.006
[33] L. Salazar-Zendeja, Models and algorithms for the minimum spanning tree interdiction problem, Doctoral dissertation, Centrale Lille Institut, 2022.
[34] A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, vol. 24, Springer Science and Business Media, 2003.
[35] J.A. Sefair and J.C. Smith, Dynamic shortest-path interdiction, Networks 68 (2016), no. 4, 315–330. https://doi.org/10.1002/net.21712
[36] J.A. Sefair and J.C. Smith, Exact algorithms and bounds for the dynamic assignment interdiction problem, Naval Research Logistics (NRL) 64 (2017), no. 5, 373–387. https://doi.org/10.1002/nav.21753
[37] J.C. Smith and Y. Song, A survey of network interdiction models and algorithms, European J. Oper. Res. 283 (2020), no. 3, 797–811. https://doi.org/10.1016/j.ejor.2019.06.024
[38] R. Steinrauf, A network interdiction model, Master’s thesis, Naval Postgraduate School, Monterey, CA, 1991.
[39] K.M. Sullivan, D.P. Morton, F. Pan, and J. Cole Smith, Securing a border under asymmetric information, Naval Research Logistics (NRL) 61 (2014), no. 2, 91–100. https://doi.org/10.1002/nav.21567
[40] J. Tayyebi, A.M. Deaconu, H. Bigdeli, and M. Niksirat, Shortest path interdiction problem with convex piecewise-linear costs, Comput. Appl. Math. 42 (2023), no. 7, 309. https://doi.org/10.1007/s40314-023-02445-0
[41] J. Tayyebi, A. Mitra, and J.A. Sefair, The continuous maximum capacity path interdiction problem, European J. Oper. Res. 305 (2023), no. 1, 38–52. https://doi.org/10.1016/j.ejor.2022.05.028
[42] A. Washburn and R.K. Wood, Two-person zero-sum games for network interdiction, Oper. Res. 43 (1994), no. 2, 243–251. https://doi.org/10.1287/opre.43.2.243
[43] N. Wei, J.L. Walteros, and F.M. Pajouh, Integer programming formulations for minimum spanning tree interdiction, INFORMS Journal on Computing 33 (2021), no. 4, 1461–1480. https://doi.org/10.1287/ijoc.2020.1018
[44] R.K. Wood, Deterministic network interdiction, Math. Comput. Model. 17 (1993), no. 2, 1–18. https://doi.org/10.1016/0895-7177(93)90236-R
[45] J. Yang, J.S. Borrero, O.A. Prokopyev, and D. Saur´e, Sequential shortest path interdiction with incomplete information and limited feedback, Decis. Anal. 18 (2021), no. 3, 218–244.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 27 May 2026

Files

Share

How to cite

Statistics