论文标题
有向图的燃烧数量：边界和计算复杂性
The Burning Number of Directed Graphs: Bounds and Computational Complexity
论文作者
论文摘要
Bonato等人最近引入了图的燃烧数量。尽管他们提到燃烧的数字自然而然地是定向图，但对此尚未进行进一步的研究。在这里，我们介绍了针对有向图的图形燃烧，并研究了相应燃烧数量的边界以及找到该数字的硬度。我们从简单的算法和示例中得出尖锐的边界。硬度问题产生了更令人惊讶的结果：发现有向树的燃烧数量是NP刺，但FPT；但是，对于DAG来说，它是W [2] - 完整的。最后，我们给出了一种固定参数算法，以找到燃烧数量的DIGRAPH，其参数受系统发育网络的研究启发。
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 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.
