| Title: |
On Graph Burning and Edge Burning |
| Authors: |
Italiano, Giuseppe F.; Konstantinidis, Athanasios L.; Kashyop, Manas Jyoti |
| Contributors: |
Giuseppe F. Italiano and Athanasios L. Konstantinidis and Manas Jyoti Kashyop |
| Publisher Information: |
Schloss Dagstuhl – Leibniz-Zentrum für Informatik |
| Publication Year: |
2025 |
| Collection: |
DROPS - Dagstuhl Research Online Publication Server (Schloss Dagstuhl - Leibniz Center for Informatics ) |
| Subject Terms: |
Burning Number; Graph Burning; Edge Burning; Approximation |
| Description: |
Graph burning is a deterministic, discrete-time process that models how influence or contagion spreads in a graph. Initially, all vertices are unburned. At each round, one new vertex is chosen to burn. Once a vertex is burned, in the next round each of its unburned neighbors become burned. The process ends when all vertices are burned. The burning number of a graph is the minimum number of rounds needed for the process to end. Very recently, a variant called edge burning was introduced, where instead of vertices we burn edges: at each round one new edge is burned. Once an edge is burned, in the next round all its unburned incident edges become burned. The edge burning number is the minimum number of rounds that are needed to burn all the edges. In this paper, we present a systematic study of edge burning and provide some new results for graph burning. First, we show a tight relationship between the edge burning number and the burning number of a given graph: specifically, their absolute difference is at most 1. Moreover, we show that the edge burning number of a graph is equal to the graph burning number of its line graph. On the computation complexity side, we show that the edge burning problem is NP-complete, but can be solved in linear time on paths, split graphs, and cographs. Furthermore, we give an XP algorithm when the edge burning problem is parameterized by the diameter of the input graph and a linear kernel when parameterized by the neighborhood diversity. For the graph burning problem, we provide 2-approximation algorithms when either the solution is part of the input or forced to form a path. |
| Document Type: |
article in journal/newspaper; conference object |
| File Description: |
application/pdf |
| Language: |
English |
| Relation: |
Is Part Of OASIcs, Volume 132, From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday (2025); https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Grossi.4 |
| DOI: |
10.4230/OASIcs.Grossi.4 |
| Availability: |
https://doi.org/10.4230/OASIcs.Grossi.4; https://nbn-resolving.org/urn:nbn:de:0030-drops-238039; https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Grossi.4 |
| Rights: |
https://creativecommons.org/licenses/by/4.0/legalcode |
| Accession Number: |
edsbas.9C0D1990 |
| Database: |
BASE |