pith. sign in

arxiv: 1907.07450 · v1 · pith:RLWPDG5Dnew · submitted 2019-07-17 · 💻 cs.DM · math.CO

Online Firefighting on Grids

Marc Demange , David Ellison , Raffaella Gentilini This is my paper

Pith reviewed 2026-05-24 20:08 UTC · model grok-4.3

classification 💻 cs.DM math.CO
keywords firefighter problemonline algorithmsgrid graphsfire containmentsufficient conditions
0
0 comments X

The pith

Sufficient conditions on firefighter sequences allow containing the fire on infinite square grids in the online setting.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines the online firefighter problem on infinite square grids, where the number of firefighters available each turn is revealed only as the process unfolds. It establishes sufficient conditions on the sequence of firefighter numbers that guarantee the fire can be contained using appropriate placement strategies. A sympathetic reader would care because containing spreading processes like fire or infection on grids is a practical concern, and the online constraint makes the model more applicable to real-time decision making without advance knowledge of resources.

Core claim

The authors provide a set of sufficient conditions that allow solving the online firefighting problem on infinite square grids and illustrate the corresponding fire containment strategies.

What carries the argument

Sufficient conditions on the online firefighter sequence together with explicit containment strategies on the grid.

Load-bearing premise

The grid is infinite with fire spreading simultaneously to all four adjacent unprotected cells each time step.

What would settle it

A sequence of firefighter numbers that meets the sufficient conditions but for which no strategy contains the fire on the infinite grid.

Figures

Figures reproduced from arXiv: 1907.07450 by David Ellison, Marc Demange, Raffaella Gentilini.

Figure 1
Figure 1. Figure 1: Online strategy to encircle the fire with (exactly) one firefighter available at each turn of the game 1, . . . , N − 1, until Condition (1) gets fulfilled at turn N. The general case, where Player 1 eventually receives at least one firefighter on each turn until Condition (1) is accomplished, is slightly more in involved. Roughly, it is solved as follows. As far as Player 1 receives fj > 1 firefighters at… view at source ↗
Figure 2
Figure 2. Figure 2: Winning the fire online with at least one firefighter eventually always available until Condition (1) is satisfied. far as we get 1 firefighter we keep on building the two diagonal walls along y = x−M, y = −x+M. As soon as we receive strictly more than one firefighter, say at turn P ≥ M, we use the extra fP −1 firefighters to surround the fire. More precisely, we stop building one of the two walls, say the… view at source ↗
read the original abstract

The Firefighter Problem (FP) is a graph problem originally introduced in 1995 to model the spread of a fire in a graph, which has attracted considerable attention in the literature. The goal is to devise a strategy to employ a given sequence of firefighters on strategic points in the graph in order to contain efficiently the fire (which spreads from each unprotected vertex to all of it neighbours on successive time steps). Recently, an online version of FP---where the number of firefighters available at each turn are revealed in real-time--- has been introduced in the literature and studied on trees. In this paper, we consider the online containment of fire on square grids. In particular, we provide a set of sufficient conditions that allow to solve the online version of the firefighting problem on infinite square grids, illustrating the corresponding fire containment strategies.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 4 minor

Summary. The paper examines the online Firefighter Problem on infinite square grids, where the number of available firefighters per time step is revealed only at runtime. It states a collection of sufficient conditions on the firefighter sequence under which the fire can be contained and supplies explicit containment strategies that realize those conditions.

Significance. The result supplies the first explicit sufficient conditions and concrete strategies for the online variant on grids, extending the tree results cited in the introduction. The sufficiency framing and the provision of explicit strategies are constructive strengths that allow direct verification of the claimed containment.

minor comments (4)
  1. [§2] §2 (Preliminaries): the online model definition should explicitly restate the four-neighbor adjacency and simultaneous spread rule used throughout the strategy constructions, even if standard.
  2. [Theorem 3.1] Theorem 3.1 and the following strategy description: the proof sketch refers to an 'infinite grid quadrant' without specifying the precise boundary handling at the origin; add a short paragraph clarifying that the origin is protected at time 0.
  3. [Figure 2] Figure 2: the time-step labels on the grid diagrams are difficult to read at the printed size; increase font size or add a supplementary table listing the firefighter placements per step.
  4. [§4] §4 (Discussion): the paragraph on possible extensions to finite grids cites no prior finite-grid results; add the relevant references.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work on sufficient conditions and explicit strategies for the online firefighter problem on infinite grids, and for the recommendation of minor revision. No major comments appear in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper claims to provide sufficient conditions and explicit containment strategies for the online firefighter problem on infinite grids. No equations, fitted parameters, predictions, or derivations appear in the abstract or described approach. The result is scoped to sufficiency rather than necessity, rests on standard 4-neighbor grid definitions, and contains no self-citation load-bearing steps, ansatz smuggling, or renaming of known results. The central claim is self-contained against external graph-theoretic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard definitions of the firefighter problem and grid graphs with no free parameters, invented entities, or ad-hoc axioms introduced.

axioms (2)
  • domain assumption Infinite square grid with four-neighbor adjacency and simultaneous spread to unprotected neighbors each turn.
    Core modeling choice stated in the problem definition.
  • domain assumption Online revelation of firefighter counts at the start of each turn.
    Defines the online variant as introduced in prior work.

pith-pipeline@v0.9.0 · 5664 in / 1144 out tokens · 32700 ms · 2026-05-24T20:08:26.470165+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

  1. [1]

    Firefighting on Trees Beyond Integrality Gaps

    David Adjiashvili, Andrea Baggio and Rico Zenklusen. Firefighting on Trees Beyond Integrality Gaps. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposi um on Discrete Algorithms (SODA2017), pp. 2364-2383, 2017

    work page 2017

  2. [2]

    Ap- proximability of the Firefighter Problem

    Elliot Anshelevich, Deeparnab Chakrabarty , Ameya Hate a nd Chaitanya Swamy . Ap- proximability of the Firefighter Problem . Algorithmica 62 (1): 520-536, 2012

    work page 2012

  3. [3]

    On- line firefighting on trees

    Pierre Coupechoux, Marc Demange, David Ellison, and Bert rand Jouve. On- line firefighting on trees . International Symposium on Combinatorial Optimization (ISCO2018), 2018

    work page 2018

  4. [4]

    Firefighting on trees

    Pierre Coupechoux, Marc Demange, David Ellison, Bertran d Jouve. Firefighting on trees. Theoretical Computer Science. In press - available online , 2019

    work page 2019

  5. [5]

    Fomin, Pinar Heggernes, and Erik Jan van Leeuwen

    Fedor V. Fomin, Pinar Heggernes, and Erik Jan van Leeuwen. The Firefighter Problem on Graph Classes . Theoretical Computer Science, 613: 38-50, 2016

    work page 2016

  6. [6]

    The Firefighter Problem for Graphs of Maximum Degree Three

    Stephen Finbow , Andrew King, Gary Macgillivray , and Rome o Rizzi. The Firefighter Problem for Graphs of Maximum Degree Three . Discrete Mathematics, 307: 2094-2105, 2007

    work page 2094

  7. [7]

    The Firefighter Problem: a survey of results, directions and questions

    Stephen Finbow and Gary MacGillivray . The Firefighter Problem: a survey of results, directions and questions . Australasian Journal of Combinatorics, 43: 57-78, 2009

    work page 2009

  8. [8]

    Ro driguez, and Manuel Lozano

    Carlos Garcia-Martinez, Christian Blum, Francisco J. Ro driguez, and Manuel Lozano. The Firefighter Problem . Computers & Operations Research 20: 55-66, 2015

    work page 2015

  9. [9]

    Hartnell

    Bert L. Hartnell. Firefighter! An application of domination. . Proc. of 25th Manitoba Conference on Combinatorial Mathematics and Computing, 19 95

    work page

  10. [10]

    Average firefighting on infinite grids

    Margaret-Ellen Messinger . Average firefighting on infinite grids . Australasian Journal of Combinatorics, 41: 15-28, 2008

    work page 2008

  11. [11]

    Firefighting on the triangular grid

    Margaret-Ellen Messinger . Firefighting on the triangular grid . Journal of Combinato- rial Mathematics and Combinatorial Computing, 63: 37-45,2 007

    work page

  12. [12]

    Ng and Paul Raff

    K.L. Ng and Paul Raff. A generalization of the firefighter problem on Z × Z. Discrete Applied Mathematics, 156 (5): 730-745,2008

    work page 2008

  13. [13]

    Ping Wang and Stephanie A. Moeller . Fire Control on Graphs . Journal of Combinato- rial Mathematics and Combinatorial Computing, 41: 19-34, 2 002. 8

    work page