2025/05/16 by Althoetmar, Julius, Schade, Jamico, Schürenberg, Torben · 1 citation
#05Cxx #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #G.2.2
paper · doi:10.48550/arxiv.2505.11082
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 a characterization for the graphs with ffn(G)=1 and ffn(G)=2 as well as almost sharp bounds 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. Based on some plausible conjectures, we also prove that this decision problem is neither NP-hard for graphs with bounded treewidth nor for constant m.