On the Completeness of Several Fortification-Interdiction Games in the Polynomial Hierarchy

References

• [1] Addis B, Di Summa M, Grosso A (2013) Identifying critical nodes in undirected graphs: Complexity results and polynomial algorithms for the case of bounded treewidth. Discrete Appl. Math. 161(16):2349–2360.Crossref, Google Scholar
• [2] Arulselvan A, Commander CW, Elefteriadou L, Pardalos PM (2009) Detecting critical nodes in sparse graphs. Comput. Oper. Res. 36(7):2193–2200.Crossref, Google Scholar
• [3] Assimakopoulos N (1987) A network interdiction model for hospital infection control. Comput. Biology Medicine 17(6):413–422.Crossref, Google Scholar
• [4] Baggio A, Carvalho M, Lodi A, Tramontani A (2021) Multilevel approaches for the critical node problem. Oper. Res. 69(2):486–508.Link, Google Scholar
• [5] Barbosa F, Agra A, de Sousa A (2021) The minimum cost network upgrade problem with maximum robustness to multiple node failures. Comput. Oper. Res. 136:105453.Crossref, Google Scholar
• [6] Brown G, Carlyle M, Salmerón J, Wood R (2006) Defending critical infrastructure. Interfaces 36(6):530–544.Link, Google Scholar
• [7] Caprara A, Carvalho M, Lodi A, Woeginger GJ (2014) A study on the computational complexity of the bilevel knapsack problem. SIAM J. Optim. 24(2):823–838.Crossref, Google Scholar
• [8] Caprara A, Carvalho M, Lodi A, Woeginger GJ (2016) Bilevel knapsack with interdiction constraints. INFORMS J. Comput. 28(2):319–333.Link, Google Scholar
• [9] Chen F, Wang R, Xu Z, Liu H, Wang M (2023) A quantified multi-stage optimization method for resource allocation of electric grid defense planning. Electric Power Systems Res. 220:109284.Crossref, Google Scholar
• [10] Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to Algorithms, 3rd ed. (MIT Press, Cambridge, MA).Google Scholar
• [11] Cormican KJ, Morton DP, Wood RK (1998) Stochastic network interdiction. Oper. Res. 46(2):184–197.Link, Google Scholar
• [12] Delgadillo A, Arroyo JM, Alguacil N (2010) Analysis of electric grid interdiction with line switching. IEEE Trans. Power Systems 25(2):633–641.Crossref, Google Scholar
• [13] Della Croce F, Scatamacchia R (2020) An exact approach for the bilevel knapsack problem with interdiction constraints and extensions. Math. Program. 183(1–2):249–281.Crossref, Google Scholar
• [14] DeNegre S (2011) Interdiction and discrete bilevel linear programming. Unpublished PhD thesis, Lehigh University, Bethlehem, PA.Google Scholar
• [15] Enayaty-Ahangar F, Rainwater CE, Sharkey TC (2019) A logic-based decomposition approach for multi-period network interdiction models. Omega 87:71–85.Crossref, Google Scholar
• [16] Fakhry R, Hassini E, Ezzeldin M, El-Dakhakhni W (2022) Tri-level mixed-binary linear programming: Solution approaches and application in defending critical infrastructure. Eur. J. Oper. Res. 298(3):1114–1131.Crossref, Google Scholar
• [17] Fröhlich N, Ruzika S (2021) On the hardness of covering-interdiction problems. Theoret. Comput. Sci. 871:1–15.Crossref, Google Scholar
• [18] Furini F, Ljubić I, Martin S, San Segundo P (2019) The maximum clique interdiction problem. Eur. J. Oper. Res. 277(1):112–127.Crossref, Google Scholar
• [19] Goerigk M, Lendl S, Wulf L (2024) On the complexity of robust multi-stage problems with discrete recourse. Discrete Appl. Math. 343:355–370.Crossref, Google Scholar
• [20] Israeli E, Wood RK (2002) Shortest-path network interdiction. Networks 40(2):97–111.Crossref, Google Scholar
• [21] Johannes B (2011) New classes of complete problems for the second level of the polynomial hierarchy. Unpublished PhD thesis, Technischen Universitat, Berlin.Google Scholar
• [22] Kuttler E, Ghorbani-Renani N, Barker K, González AD (2024) Protection-interdiction-restoration for resilient multi-commodity networks. Reliability Engrg. System Safety 242:109745.Crossref, Google Scholar
• [23] Lalou M, Tahraoui MA, Kheddouci H (2018) The critical node detection problem in networks: A survey. Comput. Sci. Rev. 28:92–117.Crossref, Google Scholar
• [24] Leitner M, Ljubić I, Monaci M, Sinnl M, Tanınmış K (2023) An exact method for binary fortification games. Eur. J. Oper. Res. 307(3):1026–1039.Crossref, Google Scholar
• [25] Lozano L, Smith JC (2017) A backward sampling framework for interdiction problems with fortification. INFORMS J. Comput. 29(1):123–139.Link, Google Scholar
• [26] Lozano L, Smith JC, Kurz ME (2017) Solving the traveling salesman problem with interdiction and fortification. Oper. Res. Lett. 45(3):210–216.Crossref, Google Scholar
• [27] Malaviya A, Rainwater C, Sharkey T (2012) Multi-period network interdiction problems with applications to city-level drug enforcement. IIE Trans. 44(5):368–380.Crossref, Google Scholar
• [28] Nabli A, Carvalho M, Hosteins P (2022) Complexity of the multilevel critical node problem. J. Comput. System Sci. 127:122–145.Crossref, Google Scholar
• [29] Nguyen DH, Smith JC (2024) Asymmetric stochastic shortest-path interdiction under conditional value-at-risk. IISE Trans. 56(4):398–410.Crossref, Google Scholar
• [30] Salmeron J, Wood K, Baldick R (2004) Analysis of electric grid security under terrorist threat. IEEE Trans. Power Systems 19(2):905–912.Crossref, Google Scholar
• [31] Salmeron J, Wood K, Baldick R (2009) Worst-case interdiction analysis of large-scale electric power grids. IEEE Trans. Power Systems 24(1):96–104.Crossref, Google Scholar
• [32] Stockmeyer LJ (1976) The polynomial-time hierarchy. Theoret. Comput. Sci. 3(1):1–22.Crossref, Google Scholar
• [33] Sullivan KM, Smith JC (2014) Exact algorithms for solving a Euclidean maximum flow network interdiction problem. Networks Internat. J. 64(2):109–124.Google Scholar
• [34] Sullivan KM, Morton DP, Pan F, Cole Smith J (2014) Securing a border under asymmetric information. Naval Res. Logist. 61(2):91–100.Crossref, Google Scholar
• [35] Weninger N, Fukasawa R (2023) A fast combinatorial algorithm for the bilevel knapsack problem with interdiction constraints. Del Pia A, Kaibel V, eds. Integer Programming and Combinatorial Optimization (Springer International Publishing, Cham, Switzerland), 438–452.Crossref, Google Scholar
• [36] Wood RK (1993) Deterministic network interdiction. Math. Comput. Model. 17(2):1–18.Crossref, Google Scholar
• [37] Wrathall C (1976) Complete sets and the polynomial-time hierarchy. Theoret. Comput. Sci. 3(1):23–33.Crossref, Google Scholar
• [38] Wu X, Conejo AJ (2017) An efficient tri-level optimization model for electric grid defense planning. IEEE Trans. Power Systems 32(4):2984–2994.Crossref, Google Scholar
• [39] Wu Y, Chen Z, Gong H, Feng Q, Chen Y, Tang H (2021) Defender–attacker–operator: Tri-level game-theoretic interdiction analysis of urban water distribution networks. Reliability Engrg. System Safety 214:107703.Crossref, Google Scholar