Metraipolis › archive › dc_cd28ecba6409

The Infectious Vaccination Problem: a variant of Firefighting with Spreading Defence — arXiv:2610.05459

Source: arXiv (en)
Original: https://arxiv.org/abs/2610.05459
License (as archived): CC0-1.0
Archived: 2026-10-06T16:53:28.588Z
SHA-256 of the archived text: 83bd9cdb219faac4c72bd72ee8b5bbdd2489a58661bd4ebf1608d3869c2791d4
Stable URL of this page: https://metraipolis.com/documento/dc_cd28ecba6409

How to cite

The Infectious Vaccination Problem: a variant of Firefighting with Spreading Defence — arXiv:2610.05459 — arXiv (en), https://arxiv.org/abs/2610.05459 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cd28ecba6409 (Metraipolis archive dc_cd28ecba6409, sha256 83bd9cdb219faac4c72bd72ee8b5bbdd2489a58661bd4ebf1608d3869c2791d4)

BibTeX

@misc{dccd28ecba6409,
  title = {The Infectious Vaccination Problem: a variant of Firefighting with Spreading Defence — arXiv:2610.05459},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.05459},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cd28ecba6409; sha256 83bd9cdb219faac4c72bd72ee8b5bbdd2489a58661bd4ebf1608d3869c2791d4},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.05459. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The Firefighter Problem models a spreading process (originally a fire, alternatively an infection or rumour, for example) on a graph. A defender saves a single vertex per turn; after each defence, the fire spreads to the unburned and undefended neighbours of all burning vertices. Deciding whether a strategy exists for the defender to protect some targeted number of vertices is computationally hard in graphs in general, but tractable in some restricted cases. Inspired by research into spreadable rabies vaccines for bats, we study a variant of the Firefighter problem in which defence also spreads. Some approximation results are already known for this problem; we provide algorithmic and hardness results, as well as containment results for the infinite $n$-dimensional Cartesian and strong grid graphs.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.05459 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-06T15:19:20.069Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).