DROPS

Document

DOI: 10.4230/LIPIcs.WG.2026.4

Complexity of Firefighting on Graphs

Authors: Julius Althoetmar, Jamico Schade, and Torben Schürenberg

Published in: LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)

Abstract

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".

Cite as

Julius Althoetmar, Jamico Schade, and Torben Schürenberg. Complexity of Firefighting on Graphs. In 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 376, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{althoetmar_et_al:LIPIcs.WG.2026.4,
  author =	{Althoetmar, Julius and Schade, Jamico and Sch\"{u}renberg, Torben},
  title =	{{Complexity of Firefighting on Graphs}},
  booktitle =	{52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-430-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{376},
  editor =	{Goedgebeur, Jan and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.4},
  URN =		{urn:nbn:de:0030-drops-261707},
  doi =		{10.4230/LIPIcs.WG.2026.4},
  annote =	{Keywords: Complexity, Cops and Robbers, Pursuit-Evasion}
}

Search Results

Documents authored by Althoetmar, Julius

Complexity of Firefighting on Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message