Liminal burning links burning and cooling on graphs

What the study found: Liminal burning is a two-player graph game that generalizes both burning and cooling. The paper studies its optimization parameter, the k-liminal burning number, and gives exact values and bounds for several graph families, including hypercubes.
Why the authors say this matters: The authors indicate that this framework unifies two existing graph processes and supports new results on graph families and computational complexity. They also note an exact cooling number for the n-dimensional hypercube.
What the researchers tested: The researchers defined k-liminal burning, where a Saboteur reveals k-vertex sets each round and an Arsonist must choose sources only from those sets. They analyzed the game on hypercubes, Cartesian grids and products, paths, and graphs whose vertex sets can be decomposed into many small-diameter components, and they studied computational complexity through reductions.
What worked and what didn't: Using a variant of Sperner sets, they obtained bounds and exact values for hypercubes for various k. In particular, they determined the exact cooling number of the n-dimensional hypercube to be n. They also showed liminal burning is PSPACE-complete for k >= 2 by reduction from 3-QBF, and that it is co-NP-hard in some cases even when it is likely not PSPACE-complete.
What to keep in mind: The abstract does not give the full list of exact values, bounds, or the detailed conditions for the co-NP-hardness result. It also states that several open problems remain.

Key points

• Liminal burning generalizes both burning and cooling on graphs.
• The paper studies the k-liminal burning number for hypercubes, grids, products, paths, and some decomposable graph families.
• The exact cooling number of the n-dimensional hypercube is n.
• Liminal burning is PSPACE-complete for k >= 2 via a reduction from 3-QBF.
• The paper also proves co-NP-hardness in some cases and ends with open problems.