TY - JOUR
T1 - The burning number of directed graphs
T2 - Bounds and computational complexity
AU - Janssen, Remie
PY - 2020
Y1 - 2020
N2 - The burning number of a graph was recently introduced by Bonato et al. Although they mention that the burning number generalises naturally to directed graphs, no further research on this has been done. Here, we introduce graph burning for directed graphs, and we study bounds for the corresponding burning number and the hardness of finding this number. We derive sharp bounds from simple algorithms and examples. The hardness question yields more surprising results: finding the burning number of a directed tree with one indegree-0 node is NP-hard, but FPT; however, it is W[2]complete for DAGs. Finally, we give a fixed-parameter algorithm to find the burning number of a digraph, with a parameter inspired by research in phylogenetic networks.
AB - The burning number of a graph was recently introduced by Bonato et al. Although they mention that the burning number generalises naturally to directed graphs, no further research on this has been done. Here, we introduce graph burning for directed graphs, and we study bounds for the corresponding burning number and the hardness of finding this number. We derive sharp bounds from simple algorithms and examples. The hardness question yields more surprising results: finding the burning number of a directed tree with one indegree-0 node is NP-hard, but FPT; however, it is W[2]complete for DAGs. Finally, we give a fixed-parameter algorithm to find the burning number of a digraph, with a parameter inspired by research in phylogenetic networks.
UR - http://www.scopus.com/inward/record.url?scp=85094126489&partnerID=8YFLogxK
U2 - 10.20429/TAG.2020.070108
DO - 10.20429/TAG.2020.070108
M3 - Article
AN - SCOPUS:85094126489
SN - 2470-9859
VL - 7
JO - Theory and Applications of Graphs
JF - Theory and Applications of Graphs
IS - 1
M1 - 8
ER -