Competing fires spread on signed graphs to maximize same color reach
Burning Signed Graphs
Discrete MathematicsComputer Science and Game Theory
Summary
This paper studies a puzzle where two fires, each with a different color, spread across a network of connected points. The connections between points have signs that decide if a fire changes color as it spreads. Each turn, a player starts a new fire of their chosen color, and the fires continue growing. The goal is to see how many points can be covered by fires of one color, described by a number called the plurality number. The authors connect this puzzle to a type of code and explore how hard it is to figure out the best way to win.
What this means in practice
- •For network security teams: Assess limits of simulating competing spread processes on signed networks to improve containment strategies.
- •For game designers: Use findings to design strategic games where player-controlled spreading processes interact over complex networks.
A theory result. No direct application yet.
Authors
Shaun Fallat, Himanshu Gupta, Kamyar Khodamoradi, Sandra Zilles
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.