{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T15:11:30Z","timestamp":1778166690739,"version":"3.51.4"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"2-3","license":[{"start":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T00:00:00Z","timestamp":1773705600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T00:00:00Z","timestamp":1773705600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2026,5]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>In the classical firefighter game, a fire breaks out on some vertices of an undirected connected graph at time zero. At each subsequent time step, a fixed number of firefighters can protect one vertex each from catching fire. Afterwards, the fire spreads from each burning vertex to every adjacent vertex that is neither burning nor defended. The game ends when the fire can no longer spread. The goal is to find a defense strategy that maximizes the number of non-burning (saved) vertices. In this work, we first revisit the classical integer linear programming formulation and then present several improvements for it, as well as two new formulations and tighter bounds on the maximum duration of the game. Moreover, we relax the classical assumptions that all vertices have uniform values and costs, i.e., we allow vertices to have different values and costs for being defended. Furthermore, instead of a fixed number of firefighters, we are given a defense budget that we can spend each time step to defend the vertices. We call this the cost-value firefighter game. We present three different integer linear programming formulations for the problem, along with a series of inequalities to strengthen the formulations and tight bounds on the maximum duration of the game.<\/jats:p>","DOI":"10.1007\/s10479-026-07096-y","type":"journal-article","created":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T01:52:27Z","timestamp":1773712347000},"page":"839-878","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Advancing firefighter games: novel integer programming formulations and the cost-value model"],"prefix":"10.1007","volume":"360","author":[{"given":"Marta","family":"Baldomero-Naranjo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5013-3448","authenticated-orcid":false,"given":"J\u00f6rg","family":"Kalcsics","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antonio M.","family":"Rodr\u00edguez-Ch\u00eda","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Catriona","family":"Wedderburn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,3,17]]},"reference":[{"key":"7096_CR1","doi-asserted-by":"crossref","unstructured":"Blum, C., Blesa, M. J., Garc\u00eda-Mart\u00ednez, C., Rodr\u00edguez, F. J., & Lozano, M. (2014). The firefighter problem: Application of hybrid ant colony optimization algorithms. In: Blum, C., Ochoa, G. (eds) Evolutionary Computation in Combinatorial Optimisation, Granada, pages 218\u2013229.","DOI":"10.1007\/978-3-662-44320-0_19"},{"issue":"4","key":"7096_CR2","doi-asserted-by":"publisher","first-page":"1322","DOI":"10.1137\/100791130","volume":"24","author":"L Cai","year":"2010","unstructured":"Cai, L., Cheng, Y., Verbin, E., & Zhou, Y. (2010). Surviving rates of graphs with bounded treewidth for the firefighter problem. SIAM Journal on Discrete Mathematics, 24(4), 1322\u20131335.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"7096_CR3","doi-asserted-by":"crossref","unstructured":"Chen, X., Hu, X., Wang, C., & Zhang, Y. (2017). Continuous firefighting on infinite square grids. In International Conference on Theory and Applications of Models of Computation, pages 158\u2013171. Springer.","DOI":"10.1007\/978-3-319-55911-7_12"},{"key":"7096_CR4","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1016\/j.dam.2014.11.019","volume":"210","author":"V Costa","year":"2016","unstructured":"Costa, V., Dantas, S., Dourado, M. C., Penso, L., & Rautenbach, D. (2016). Slash and burn on graphs \u2013 firefighting with general weights. Discrete Applied Mathematics, 210, 4\u201313. LAGOS&apos;13: Seventh Latin-American Algorithms, Graphs, and Optimization Symposium, Playa del Carmen, M\u00e9xico \u2014 2013.","journal-title":"Discrete Applied Mathematics"},{"key":"7096_CR5","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/j.tcs.2019.01.040","volume":"794","author":"P Coupechoux","year":"2019","unstructured":"Coupechoux, P., Demange, M., Ellison, D., & Jouve, B. (2019). Firefighting on trees. Theoretical Computer Science, 794, 69\u201384.","journal-title":"Theoretical Computer Science"},{"key":"7096_CR6","first-page":"793","volume":"6","author":"B Delaunay","year":"1934","unstructured":"Delaunay, B. (1934). Sur la sph\u00e8re vide (on the empty sphere). Bulletin de l\u2019Acad\u00e9mie des Sciences de l\u2019URSS, Classe des Sciences Math\u00e9matiques et Naturelles, 6, 793\u2013800.","journal-title":"Bulletin de l\u2019Acad\u00e9mie des Sciences de l\u2019URSS, Classe des Sciences Math\u00e9matiques et Naturelles"},{"issue":"17","key":"7096_CR7","doi-asserted-by":"publisher","first-page":"2257","DOI":"10.1016\/j.dam.2007.06.002","volume":"155","author":"M Develin","year":"2007","unstructured":"Develin, M., & Hartke, S. G. (2007). Fire containment in grids of dimension three and higher. Discrete Applied Mathematics, 155(17), 2257\u20132268.","journal-title":"Discrete Applied Mathematics"},{"key":"7096_CR8","first-page":"167","volume":"94","author":"C Duffy","year":"2015","unstructured":"Duffy, C., & MacGillivray, G. (2015). An analysis of the weighted firefighter problem. Journal of Combinatorial Mathematics and Combinatorial Computing, 94, 167\u2013175.","journal-title":"Journal of Combinatorial Mathematics and Combinatorial Computing"},{"key":"7096_CR9","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/j.epidem.2018.04.003","volume":"24","author":"J Enright","year":"2018","unstructured":"Enright, J., & Kao, R. R. (2018). Epidemics on dynamic networks. Epidemics, 24, 88\u201397.","journal-title":"Epidemics"},{"key":"7096_CR10","doi-asserted-by":"crossref","unstructured":"Enright, J., & Meeks, K. (2015). Deleting edges to restrict the size of an epidemic: A new application for treewidth. In Zaixin Lu, Donghyun Kim, Weili Wu, Wei Li, and Ding-Zhu Du, editors, Combinatorial Optimization and Applications, pages 574\u2013585, Cham. Springer International Publishing.","DOI":"10.1007\/978-3-319-26626-8_42"},{"issue":"3","key":"7096_CR11","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1002\/jgt.21673","volume":"73","author":"L Esperet","year":"2013","unstructured":"Esperet, L., Van den Heuvel, J., Maffray, F., & Sipma, F. (2013). Fire containment in planar graphs. Journal of Graph Theory, 73(3), 267\u2013279.","journal-title":"Journal of Graph Theory"},{"key":"7096_CR12","unstructured":"Finbow, S., Hartnell, B., Li, Q., & Schmeisser, K. (2000). On minimizing the effects of fire or a virus on a network. JCMCC. The Journal of Combinatorial Mathematics and Combinatorial Computing, 33, 01."},{"issue":"16","key":"7096_CR13","doi-asserted-by":"publisher","first-page":"2094","DOI":"10.1016\/j.disc.2005.12.053","volume":"307","author":"S Finbow","year":"2007","unstructured":"Finbow, S., King, A., MacGillivray, G., & Rizzi, R. (2007). The firefighter problem for graphs of maximum degree three. Discrete Mathematics, 307(16), 2094\u20132105. EuroComb &apos;03 - Graphs and Algorithms.","journal-title":"Discrete Mathematics"},{"key":"7096_CR14","first-page":"57","volume":"43","author":"S Finbow","year":"2009","unstructured":"Finbow, S., & MacGillivray, G. (2009). The Firefighter Problem: A survey of results, directions and questions. Australasian Journal of Combinatorics, 43, 57\u201378.","journal-title":"Australasian Journal of Combinatorics"},{"key":"7096_CR15","doi-asserted-by":"crossref","unstructured":"Gabriel, K. R., & Sokal, R. R. (1969). A new statistical approach to geographic variation analysis. Systematic Biology,18(3), 259\u2013278.","DOI":"10.2307\/2412323"},{"key":"7096_CR16","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.cor.2015.02.004","volume":"60","author":"C Garc\u00eda-Mart\u00ednez","year":"2015","unstructured":"Garc\u00eda-Mart\u00ednez, C., Blum, C., Rodr\u00edguez, F. J., & Lozano, M. (2015). The firefighter problem: Empirical results on random graphs. Computers & Operations Research, 60, 55\u201366.","journal-title":"Computers & Operations Research"},{"key":"7096_CR17","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1016\/j.disc.2014.06.020","volume":"337","author":"T Gavenc\u0306iak","year":"2014","unstructured":"Gavenc\u0306iak, T., Kratochv\u00edl, J., & Pra\u0142at, P. (2014). Firefighting on square, hexagonal, and triangular grids. Discrete Mathematics, 337, 142\u2013155.","journal-title":"Discrete Mathematics"},{"key":"7096_CR18","unstructured":"Goodman, B. (2006). To stem widespread extinction, scientists airlift frogs in carry-on bags. The New York Times."},{"key":"7096_CR19","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1016\/j.tcs.2015.06.002","volume":"593","author":"P Gordinowicz","year":"2015","unstructured":"Gordinowicz, P. (2015). Planar graph is on fire. Theoretical Computer Science, 593, 160\u2013164.","journal-title":"Theoretical Computer Science"},{"key":"7096_CR20","unstructured":"Hartnell, B.\u00a0L. (1995). Firefighter! An application of domination. Presentation at the 24th Manitoba Conference on Combinatorial Mathematics and Computing."},{"key":"7096_CR21","doi-asserted-by":"crossref","unstructured":"Hu, B., Windbichler, A., & Raidl, G. R. (2015). A new solution representation for the firefighter problem. In Gabriela Ochoa and Francisco Chicano (eds) Evolutionary Computation in Combinatorial Optimization\u201415th European Conference, EvoCOP 2015, Copenhagen, Denmark, April 8\u201310, pages 25\u201335.","DOI":"10.1007\/978-3-319-16468-7_3"},{"issue":"2","key":"7096_CR22","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1587\/transinf.E94.D.196","volume":"E94\u2013D","author":"Y Iwaikawa","year":"2011","unstructured":"Iwaikawa, Y., Kamiyama, N., & Matsui, T. (2011). Improved approximation algorithms for firefighter problem on trees. IEICE Transactions on Information and Systems, E94\u2013D(2), 196\u2013199.","journal-title":"IEICE Transactions on Information and Systems"},{"key":"7096_CR23","first-page":"83","volume":"47","author":"G MacGillivray","year":"2003","unstructured":"MacGillivray, G., & Wang, P. (2003). On the firefighter problem. Journal of Combinatorial Mathematics and Combinatorial Computing, 47, 83\u201396.","journal-title":"Journal of Combinatorial Mathematics and Combinatorial Computing"},{"issue":"3","key":"7096_CR24","doi-asserted-by":"publisher","first-page":"1312","DOI":"10.1111\/itor.13524","volume":"32","author":"AB Mendes","year":"2025","unstructured":"Mendes, A. B., & e Alvelos, F. P. (2025). A robust optimisation approach for the placement of forest fire suppression resources. International Transactions in Operational Research, 32(3), 1312\u20131342.","journal-title":"International Transactions in Operational Research"},{"key":"7096_CR25","doi-asserted-by":"crossref","unstructured":"Michalak, K. (2020). Evolutionary graph-based V+E optimization for protection against epidemics. In Parallel Problem Solving from Nature\u2013PPSN XVI: 16th International Conference, PPSN 2020, Leiden, The Netherlands, September 5-9, 2020, Proceedings, Part II 16, pages 399\u2013412. Springer.","DOI":"10.1007\/978-3-030-58115-2_28"},{"issue":"2","key":"7096_CR26","doi-asserted-by":"publisher","first-page":"937","DOI":"10.1007\/s10479-021-04393-6","volume":"320","author":"O Ozkan","year":"2023","unstructured":"Ozkan, O., & Kilic, S. (2023). UAV routing by simulation-based optimization approaches for forest fire risk mitigation. Annals of Operations Research, 320(2), 937\u2013973.","journal-title":"Annals of Operations Research"},{"key":"7096_CR27","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1016\/j.epidem.2014.07.003","volume":"10","author":"L Pellis","year":"2015","unstructured":"Pellis, L., Ball, F., Bansal, S., Eames, K., House, T., Isham, V., & Trapman, P. (2015). Eight challenges for network epidemic models. Epidemics, 10, 58\u201362.","journal-title":"Epidemics"},{"issue":"2","key":"7096_CR28","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1007\/s00373-012-1265-9","volume":"30","author":"P Pra\u0142at","year":"2014","unstructured":"Pra\u0142at, P. (2014). Graphs with average degree smaller than $$\\frac{30}{11}$$ burn slowly. Graphs and Combinatorics, 30(2), 455\u2013470.","journal-title":"Graphs and Combinatorics"},{"issue":"2","key":"7096_CR29","doi-asserted-by":"publisher","first-page":"739","DOI":"10.1111\/itor.12638","volume":"27","author":"N Ramos","year":"2020","unstructured":"Ramos, N., de Souza, C. C., & de Rezende, P. J. (2020). A matheuristic for the firefighter problem on graphs. International Transactions in Operational Research, 27(2), 739\u2013766.","journal-title":"International Transactions in Operational Research"},{"key":"7096_CR30","first-page":"11","volume":"232","author":"M R\u00f6nnqvist","year":"2015","unstructured":"R\u00f6nnqvist, M., D\u2019Amours, S., Weintraub, A., Jofre, A., Gunn, E., Haight, R. G., Martell, D., Murray, A. T., & Romero, C. (2015). Operations research challenges in forestry: 33 open problems. Annals of Operations Research, 232, 11\u201340.","journal-title":"Annals of Operations Research"},{"issue":"6","key":"7096_CR31","doi-asserted-by":"publisher","first-page":"3296","DOI":"10.1111\/itor.13316","volume":"30","author":"M R\u00f6nnqvist","year":"2023","unstructured":"R\u00f6nnqvist, M., Martell, D., & Weintraub, A. (2023). Fifty years of operational research in forestry. International Transactions in Operational Research, 30(6), 3296\u20133328.","journal-title":"International Transactions in Operational Research"},{"key":"7096_CR32","unstructured":"Tennenholtz, G., Caramanis, C., & Mannor, S. (2017). The stochastic firefighter problem. CoRR, arXiv:1711.08237."},{"key":"7096_CR33","unstructured":"Wagner, C. (2021). A new survey on the firefighter problem. Master\u2019s thesis, University of Victoria."},{"issue":"4","key":"7096_CR34","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1007\/s10878-012-9541-4","volume":"27","author":"W Wang","year":"2014","unstructured":"Wang, W., Finbow, S., & Wang, P. (2014). A lower bound of the surviving rate of a planar graph with girth at least seven. Journal of Combinatorial Optimization, 27(4), 621\u2013642.","journal-title":"Journal of Combinatorial Optimization"},{"issue":"1","key":"7096_CR35","doi-asserted-by":"publisher","first-page":"917","DOI":"10.1007\/s10479-017-2598-9","volume":"283","author":"Z Yang","year":"2019","unstructured":"Yang, Z., Guo, L., & Yang, Z. (2019). Emergency logistics for wildfire suppression based on forecasted disaster evolution. Annals of Operations Research, 283(1), 917\u2013937.","journal-title":"Annals of Operations Research"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-026-07096-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10479-026-07096-y","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-026-07096-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T14:24:07Z","timestamp":1778163847000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10479-026-07096-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,17]]},"references-count":35,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[2026,5]]}},"alternative-id":["7096"],"URL":"https:\/\/doi.org\/10.1007\/s10479-026-07096-y","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,17]]},"assertion":[{"value":"20 March 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 February 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 March 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose, and neither have they any conflict of interest to declare that is relevant to the content of this article. All authors certify that they have no affiliations with or involvement in any organization or entity with any financial interest or non-financial interest in the subject matter or materials discussed in this manuscript. The authors have no financial or proprietary interests in any material discussed in this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"This article does not contain any studies with human participants or animals performed by any of the authors.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}}]}}