CS Paper Radar

The Infectious Vaccination Problem: a variant of Firefighting with Spreading Defence

Jessica Enright, Melissa A. Huggan, Ethan Hunter-Frankland, Margaret-Ellen Messinger, Dylan Pearson

cs.DS math.CO ·submitted 2026-10-04 19:09 UTC · v1

Abstract

The Firefighter Problem models a spreading process (originally a fire, alternatively an infection or rumour, for example) on a graph. A defender saves a single vertex per turn; after each defence, the fire spreads to the unburned and undefended neighbours of all burning vertices. Deciding whether a strategy exists for the defender to protect some targeted number of vertices is computationally hard in graphs in general, but tractable in some restricted cases. Inspired by research into spreadable rabies vaccines for bats, we study a variant of the Firefighter problem in which defence also spreads. Some approximation results are already known for this problem; we provide algorithmic and hardness results, as well as containment results for the infinite $n$-dimensional Cartesian and strong grid graphs.

Comment
17 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Multi-seed information diffusion with varying reproduction

cs.DS cs.DM ·2026-11-15 ·Erin Meger, Arianne Nantel, Nicholas Saloufakos, Jessica Enright
position similarity 0.64
Abstract · 11 page, 2 figures

We define the $S_hR_k$-process that generalizes the notion of Hamiltonicity through the lense of information diffusion. We say that a graph is $S_hR_k$-infectable if it can be fully infected by transmission trees seeded by at most $h$ initial infections in which each infection leads to at most $k$ others; or, equivalently, if it can be exactly vertex-covered by at most $h$ trees of degree at most $k$. While determining $S_hR_k$ infectability is NP-hard in general, we argue fixed-parameter tractability when parameterised by treewidth. Additionally, we give computational experimental results comparing the performance of several natural heuristics for minimising the number of initial infections required to an optimal LP-based approach on several standard complex network models. We find that a uniformly random approach outperforms greedy heuristics based on degree or clustering.

0.34

Burning Signed Graphs

cs.DM math.COcs.GT ·2026-10-01 ·Shaun Fallat, Himanshu Gupta, Kamyar Khodamoradi, Sandra Zilles
theory similarity 0.60
Abstract

We introduce and analyze a new model of graph burning, in which two competing fires (coloured yellow and green) ignite vertices of a given signed graph and propagate along its edges. The boolean sign of an edge determines whether a fire spreading along the edge changes colour or not. In each step, a player ignites a new vertex in a colour of their choice, while previously activated fires continue to spread. Given a signed graph $Γ$, the objective is to burn the maximum possible number of vertices in a single colour; the optimal achievable value is called the plurality number of $Γ$. We express the plurality number through Hamming distances to a binary code associated with $Γ$. In particular, the minimum plurality number over the switching class of $Γ$ equals the number of vertices minus the covering radius of this code. Under certain conditions on the signature, we determine exact values of the plurality number of signed paths. By contrast, we prove hardness results for multiple variants of the problem of determining or approximating the plurality number.

0.27

Blindfolded pursuit with delays of your choice

cs.GT ·2026-08-27 ·Torben Schürenberg, Maximilian J. Stahlberg
similarity 0.58
Abstract

We study pursuit-evasion games on graphs with a single pursuer and an invisible evader. The pursuer may assign integer travel times to the edges of the graph and specify a finite sequence of vertices to query, one per time step. The evader then chooses a walk over the same time horizon, aiming to elude all queries. With unit travel times, the setting in which the evader must move at every time step is known as the hunter and rabbit game, while the variant in which the evader can wait at a vertex can be phrased as a firefighting game: the vertices of a burning graph must be extinguished, and any vertex left burning reignites its neighbors. For both settings, we show that the power to choose travel times allows a single pursuer to succeed in polynomial time on any graph. This contrasts with unweighted graphs, where the number of hunters or firefighters needed can grow linearly in the number of vertices. If the evader, in addition to waiting, may start at an earlier time unknown to the pursuer, we show that the pursuer still wins on any graph given exponential time.

0.25

PSPACE-completeness of the Hunters and Rabbit game

cs.CC cs.DM ·2026-10-13 ·Walid Ben-Ameur, Alessandro Maddaloni
theory similarity 0.58
Abstract

In the Hunters and Rabbit game, hunters shoot at a set of vertices at each round, while an invisible rabbit must move along an edge. We prove that deciding whether a given number of hunters can guarantee capture is PSPACE-complete, even on simple bipartite graphs. The reduction uses intersection nonemptiness for inverse finite automata: one common word must put all automata in accepting states simultaneously. A clique acting as a safe haven and two families of guards force every winning strategy to simulate common transitions. Existing transformations remove the restriction on the rabbit's initial positions and yield PSPACE-completeness for the directed game with one hunter, even on oriented graphs with positive minimum outdegree. Adjusting the guard sizes also proves PSPACE-completeness of the firefighting game, in which the rabbit may remain at its current vertex.

0.18

Local Search for Almost-Spanning Square Grids in Erdős--Rényi Random Graphs

cs.DM math.PRmath.CO ·2026-09-11 ·Dávid Ferenczi, Alexander Grigoriev
theory similarity 0.57
Abstract · 18 pages, 1 figure

Finding large lattice subgraphs in sparse Erdős--Rényi random graphs is a classical problem at the interface of random graph theory and algorithms. General bounded-degree embedding and universality theorems give powerful results for broad graph families, but when specialized to square grids they operate at densities substantially larger than the grid-emergence scale. In this paper we exploit the specific geometry of the square grid. We introduce the Quarantined Local Search, a three-phase local algorithm that separates the construction of an initial boundary from the later corner-closure process and controls adaptive negative exposure through bounded pair-test histories. We prove that, for every fixed $δ\in (0,1)$, there exists $C_δ>0$ such that the algorithm embeds a $k\times k$ square grid with $k^2\le (1-δ)n$ in $G(n,p)$ with high probability whenever $p\ge C_δ\sqrt{\ln k/n}$. Thus, for $k^2=Θ(n)$, a density of order $\sqrt{\log n/n}$ is sufficient, a factor of order $\sqrt{\log n}$ above the corresponding $n^{-1/2}$ emergence scale.

0.15

Two-Colour Zig-Zag Numberlink on Rectangles: A Forbidden-Pattern Characterization, a Constructive Polynomial-Time Algorithm, and a Lean Verification

cs.DS cs.LG ·2026-10-19 ·Zzyv Zzyzek
similarity 0.56
Abstract

In Zig-Zag Numberlink, pairs of endpoints in a grid must be joined by vertex-disjoint paths that together visit every cell. The problem is NP-complete when the number of pairs is un- bounded (Adcock et al.). For a single pair it is the Hamiltonian path problem in rectangular grid graphs, solved by Itai, Papadimitriou and Szwarcfiter. Two pairs on a rectangle form the paired 2-disjoint path cover problem. We settle the case of two pairs on rectangles with the endpoints anywhere in the grid. If both sides of the rectangle are at least 11, an instance is solvable if and only if no entry of a finite catalogue of forbidden patterns occurs. The catalogue consists of a parity condition, an alternation condition on the border, a handful of local corner and edge patterns, 65 listed corner configurations, and a rule that propagates forced routes out of the corners before testing alternation. If a side is at most 10, a frontier dynamic programming algorithm decides the instance in time linear in the long side. The characterization is construc- tive. Solutions are built by deleting empty lines, splitting the rectangle by straight cuts, and splicing the pieces back together, in time O((R+C) RC). Both directions of the characterization and the correctness of the dynamic programming algorithm are verified in Lean 4. The finite case analyses, which are window certificates for the corner configurations and a check of all irreducible instances with sides 11-22, are carried out by the Lean compiler via native decide. We describe the algorithm, the catalogue, the proof structure, the compromises made in the formalization, and implementations in Python, JavaScript and C that produce identical output.

0.29

Collision-free Movement on Grids and Beyond

cs.MA cs.DS ·2026-09-25 ·Hendrik Molter, Meirav Zehavi
similarity 0.55
Abstract

We study collision-free movement problems on graphs, where the task is to coordinate a set of robots so that they reach a target formation satisfying a desired property while minimizing the total travel distance. This framework extends two classical models: (a) minimizing movement [Demaine et al., TALG '09, '14], which does not enforce collision avoidance, and (b) coordinated motion planning or multi-agent path finding [Eiben et al., SoCG '23, Deligkas et al., ICALP '24, among many others], where each robot is assigned an explicit target position. We focus on the setting where the target formation of the robots should be connected. We analyze the parameterized complexity of the problem with respect to the number of (main) robots and the total travel length on grid graphs and two natural generalizations thereof: planar graphs and unit disk graphs.

0.22

Influence of Assortativity on the SICP Spreading Process in Hypergraphs

cs.SI physics.soc-ph ·2026-11-11 ·Jelmer Stolwijk, Renze Dijkhuizen, H. A., Peters, Huijuan Wang
similarity 0.54
Abstract

Many real-world systems involve group interactions that cannot be captured by pairwise graphs. They can be better represented by hypergraphs where each hyperedge could connect an arbitrary number of nodes. The Susceptible-Infected Contact Process (SICP) has been proposed to model the spreading of information and epidemics on hypergraphs. However, how higher-order topological properties of a hypergraph influence the SICP spreading process remains understudied. In this paper, we examine the impact of hypergraph assortativity based on the Neighborhood Coefficient (NC)-the average size of hyperedges incident to a node-on the SICP spreading process. By introducing a low-complexity measure of hypergraph assortativity grounded in analysis of variance, we apply hyperdegree-preserving rewirings to real-world networks and synthetic hypergraph models to tune their assortativity. We find and explain why lower NC assortativity yields higher average epidemic prevalence and lower prevalence variance across different seed selections. This phenomenon is evident when hyperdegree-preserving rewirings are applied to real-world networks with heterogeneous topological structures, but it is largely absent when comparing synthetic random hypergraphs to their rewired counterparts.

0.15