Source-linked AI summary
Burning Signed Graphs
Shaun Fallat, Himanshu Gupta, Kamyar Khodamoradi, Sandra Zilles
TL;DR
The paper studies how two competing, differently coloured fires spread through signed graphs and how many vertices can be burned in one colour. It connects this plurality number to a binary code, deriving a covering-radius characterization across switchings, exact results for some signed paths, and hardness results for variants.
Problem
The paper asks how to characterize the maximum single-colour spread in a signed-graph burning process and how hard its computation or approximation is.
Source: §1 · pp. 1–2, §4 · p. 17Method
It defines two-colour burning on signed graphs and uses an algebraic formulation that associates reachable colourings with a binary code.
Source: §1 · p. 2Results
The minimum plurality across a switching class is characterized by the associated code’s covering radius, while special signed paths have exact values and several problem variants are NP-hard.
Source: §1 · p. 2, §5 · p. 27Takeaways & Limitations
The coding-theoretic connection frames switching-class minimization as a covering-radius problem, while general computation remains difficult in certain variants.
Source: §1 · p. 2, §5 · p. 27The set-cover construction assumes no set contains another, every set has size at least two, and the universe has no isolated elements.
Source: §4 · p. 19
Abstract
from arXiv · showhide
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 $\Gamma$, 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 $\Gamma$. We express the plurality number through Hamming distances to a binary code associated with $\Gamma$. In particular, the minimum plurality number over the switching class of $\Gamma$ 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.
1. Introduction
The paper adapts graph burning to competing fires on signed graphs, where edge signs affect the colour of spreading fire and the player chooses each new ignition colour. It studies the maximum single-colour count, relates it to coding theory, and establishes exact path results alongside hardness results.
1. Introduction
- Edge signs determine whether fire preserves or changes colour as it spreads, while the player chooses the colour of each newly ignited vertex.The model represents reinforcing or counteracting information in competing groups.Source: §1 · p. 2
- The plurality number is the largest number of vertices that can be burned in one colour.Source: §1 · p. 2
- Exact values are obtained for a subclass of signed paths, while computing or approximating plurality remains hard in several variants.The hardness results include directed graphs and processes with a predefined termination round.Source: §1 · p. 2
- The minimum plurality number within a switching class is expressed using the covering radius of a binary code associated with that class.Source: §1 · p. 2
2. Signed Burning with Two Colours
Signed graph burning uses positive and negative edges to govern the colours of spreading fires, with one new vertex ignited in a chosen colour each round. Switching preserves the signed burning number, and reachable colourings connect plurality to Hamming distance and code covering radius.
2. Signed Burning with Two Colours
- Switching by a vertex subset flips incident edge signs across the subset boundary and changes corresponding fire colours without changing termination time.The switched process has the same ignited vertices and a coordinate-wise sign-flipped configuration.Source: §2 · pp. 3–4
- Each round spreads fires to unburned vertices according to edge signs, then ignites an available vertex in yellow or green.Positive edges preserve colour and negative edges reverse it; simultaneous conflicting influences are subject to special rules.Source: §2 · pp. 2–3
- The plurality number is the maximum number of vertices burned in one colour, and it is at least ⌈n/2⌉.Reachable final colourings give equivalent maximum counts for yellow and green.Source: §2 · p. 5
- Switching-equivalent signed graphs have the same signed burning number; it is at least the unsigned burning number and equals it for balanced graphs.Every signed forest is balanced.Source: §2 · pp. 5–6
- For the illustrated unbalanced signed graph, b(G)=3 while b(Γ)=4, so the unsigned lower bound can be strict.Source: §2 · p. 6, Figure 1 · p. 6
- Reachable colourings form a binary code, and the minimum plurality across a switching class equals n minus that code’s covering radius.For a particular switch, n minus plurality is the Hamming distance from its sign vector to the code.Source: §2 · pp. 6–7
3. Plurality Number of Signed Path Graphs
This section bounds the plurality number of signed paths by analyzing Hamming-distance disagreements on negative segments and the structure of colouring blocks. It identifies conditions under which the bounds coincide and relates the minimum over path signatures, attained by the all-negative path, to a covering radius.
3. Plurality Number of Signed Path Graphs
- The lower and upper bounds coincide for Γ−, or when every interior negative segment has order not divisible by 3 and ε = 0.Here ε = 1 only when both end segments are negative and have orders congruent to 2 modulo 3.Source: §3 · pp. 7–8
- Y(Γ) ≥ Y(Γ−) = ⌊(2n + 1)/3⌋ for every signed path, with equality when n ≡ 2 (mod 3) only for Γ = Γ−.If n ≡ 2 (mod 3) and Γ ≠ Γ−, then Y(Γ) ≥ Y(Γ−) + 1.Source: §3 · pp. 8–9
- The minimum plurality over the path’s switching class is n minus the code’s covering radius, and the alternating vector for Γ− is a deep hole, unique up to global sign when n ≡ 2 (mod 3).Every signed path is balanced, so all its signatures belong to one switching class.Source: §3 · p. 9
3.1. Proof of Theorem 3.1.
- For the lower-bound construction, the proof ignites selected segment-list entries so the final coloring differs from the target only at negative-segment running entries and, when ε = 1, at v1.The segment lists contain ⌊m/3⌋ running entries for a negative segment of order m.Source: §3.1 · p. 10
- In the Theorem 3.1 proof, the final colouring differs from ΦU at the running entries of negative segments and, when ε = 1, at v1; the proof then concludes the bound in (3).The remaining ignitions are of held vertices and cause no further spreading.Source: §3.1 · p. 13
3.2. Proof of Theorem 3.2.
- Lemma 3.9 constrains burn times around singleton and order-3 blocks, and shows that adjacent vertices in different blocks that are both not held have equal burn times; singleton blocks cannot be adjacent.Source: §3.2 · p. 14
- Between consecutive singleton blocks with no singleton block between them, some intervening block has order 2 or at least 4.Source: §3.2 · p. 15
- For each negative segment of order m, the final colouring differs from ΦU on at least floor((m − 1 + e)/3) vertices, where e records the segment’s endpoint condition.This follows from the bound on the number of odd-order pieces of the colouring on the segment.Source: §3.2 · p. 16
4. Computational Complexity
This section analyzes the computational complexity of plurality optimization and threshold decisions across signed-graph variants, including directed and undirected graphs and variants with or without deadlines. It establishes NP-completeness and hardness of approximation or exact computation for the variants discussed.
Problem setup
- For directed graphs, fire spreads along incoming arcs when calculating vertex influence, and a deadline ends the process after its ignition step or when all vertices are burned.Without a deadline, the generalized plurality remains the original plurality parameter; the four variants are ordered by Cook-reducibility.Source: §4 · p. 17
Directed graphs with deadlines
- Unless P = NP, directed signed-graph plurality with deadline k has no polynomial-time (1 − 1/e + ε)-approximation for any ε > 0.The hardness also holds when all edge signs are positive.Source: §4 · pp. 17, 19
Undirected graphs with deadlines
- Unless P = NP, no polynomial-time exact algorithm computes Y_k(Γ) for an undirected signed graph with deadline k.The reduction uses positive signs, so the problem includes standard unsigned graph burning.Source: §4 · p. 19
Directed graphs without deadlines
- Unless P = NP, no polynomial-time exact algorithm computes Y(Γ) for a directed signed graph without a deadline.The Set Cover reduction uses timer and bait gadgets to enforce the ignition sequence and distinguish coverable from non-coverable instances.Source: §4 · pp. 19–21
Undirected graphs without deadlines
- Deciding whether Y(Γ) ≥ τ for an undirected signed graph without a deadline is NP-complete, ruling out polynomial-time exact computation unless P = NP.The reduction extends hardness from standard graph burning.Source: §4 · p. 21
4. Computational Complexity
- A burning sequence certifies Y(Γ) ≥ τ, and the resulting burning process can be simulated in polynomial time, placing the decision problem in NP.Source: §4 · p. 25
- Deciding whether Y(Γ) ≥ τ is NP-complete, via a polynomial reduction preserving b(G) ≤ m iff Y(Γ(G,m)) ≥ τ.The reduction is from Graph Burning, which is NP-complete.Source: §4 · pp. 25–26
- Unless P = NP, no polynomial-time exact algorithm computes Y(Γ), since one would decide Graph Burning in polynomial time.Source: §4 · p. 26
- Unless P = NP, no polynomial-time exact algorithm computes Y_k(Γ) with k as input or Y(Γ) for directed signed graphs.Source: §4 · p. 26
5. Conclusions
The paper introduces signed graph burning and the plurality number, gives exact values for special classes of signed paths, and proves NP-hardness for computing or approximating the parameter in certain variants. It also points to coding-theoretic connections and future work on signed trees and tractable subproblems.
5. Conclusions
- Signed graph burning introduces two colours and a related parameter, the plurality number, motivated by social networks with positive and negative ties.Source: §5 · p. 27
- Exact plurality numbers are derived for special classes of signed paths, while computing or approximating the parameter is NP-hard in certain variants.The paper suggests extending these results to signed trees and identifying polynomial-time solvable subproblems.Source: §5 · p. 27
- Connections between signed burning and code covering radii may yield coding-theoretic tools applicable to graph burning.Source: §5 · p. 27
7. AI Disclosure
Claude Opus 5.5 contributed to Theorem 4.6 and parts of Theorems 3.1 and 3.2; the authors independently verified all mathematical arguments and results and take responsibility for the paper.
7. AI Disclosure
- Claude Opus 5.5 contributed to Theorem 4.6 and parts of Theorems 3.1 and 3.2; all arguments and results were independently verified by the authors.Source: §7 · p. 27
- The four authors devised the remaining proofs, the signed burning model, and its related parameters, and take full responsibility for the paper.Source: §7 · p. 27