2020/01/10 by Remie Janssen, Janssen, Remie · 2 citations
Biochemistry, Genetics and Molecular Biology · #Genomics and Phylogenetic Studies #Bioinformatics and Genomic Networks
paper · pdf · doi:10.48550/arxiv.2001.03381
The burning number of a graph was recently introduced by Bonato et al.\nAlthough they mention that the burning number generalises naturally to directed\ngraphs, no further research on this has been done. Here, we introduce graph\nburning for directed graphs, and we study bounds for the corresponding burning\nnumber and the hardness of finding this number. We derive sharp bounds from\nsimple algorithms and examples. The hardness question yields more surprising\nresults: finding the burning number of a directed tree is NP-hard, but FPT;\nhowever, it is W[2]-complete for DAGs. Finally, we give a fixed-parameter\nalgorithm to find the burning number of a digraph, with a parameter inspired by\nresearch in phylogenetic networks.\n