Complexity of Firefighting on Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911589894979584 |
|---|---|
| author | Althoetmar, Julius Schade, Jamico Schürenberg, Torben |
| author_facet | Althoetmar, Julius Schade, Jamico Schürenberg, Torben |
| contents | We consider a pursuit-evasion game that describes the process of extinguishing a fire burning on the nodes of an undirected graph. We denote the minimum number of firefighters required by ffn(G) and provide almost sharp bounds to this graph parameter for complete binary trees. We show that deciding whether ffn(G) <= m for given G and m is NP-hard. Furthermore, we show that shortest strategies can have superpolynomial length, leaving open whether the problem is in NP. We provide a construction that allows for transferring these results to a well-established Cops and Robbers variant called the "Hunter and Rabbit game". |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_11082 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Complexity of Firefighting on Graphs Althoetmar, Julius Schade, Jamico Schürenberg, Torben Computational Complexity Discrete Mathematics 05Cxx F.2.2; G.2.2 We consider a pursuit-evasion game that describes the process of extinguishing a fire burning on the nodes of an undirected graph. We denote the minimum number of firefighters required by ffn(G) and provide almost sharp bounds to this graph parameter for complete binary trees. We show that deciding whether ffn(G) <= m for given G and m is NP-hard. Furthermore, we show that shortest strategies can have superpolynomial length, leaving open whether the problem is in NP. We provide a construction that allows for transferring these results to a well-established Cops and Robbers variant called the "Hunter and Rabbit game". |
| title | Complexity of Firefighting on Graphs |
| topic | Computational Complexity Discrete Mathematics 05Cxx F.2.2; G.2.2 |
| url | https://arxiv.org/abs/2505.11082 |