The Firefighter problem with dynamic defence costs.

ABSTRACT: The Firefighter Problem is a single-player game modelling the spread of a contagion (e.g. rumours, diseases) on a graph. The player's objective is to defend vertices to protect at least a given number. This problem is computationally hard, but it can be solved efficiently on certain restricted classes of graph, such as complete graphs (in constant time) and graphs with path length at most [Formula: see text] (in [Formula: see text]-time). We define The Cost Function Firefighter Problem, the first variant of the Firefighter problem that introduces vertex defence costs depending on time and game state. We show the Cost Function problem is computationally hard even for classes of trees on which the classic problem is tractable, but tractable on some very restricted graph classes (complete gra

SUBMITTER: Hunter E 

PROVIDER: S-EPMC12880756 | biostudies-literature | 2026

REPOSITORIES: biostudies-literature