文章基本信息

标题：Parameterized Complexity of Graph Burning
本地全文：下载
作者：Yasuaki Kobayashi ; Yota Otachi
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：180
页码：1-10
DOI：10.4230/LIPIcs.IPEC.2020.21
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Graph Burning asks, given a graph G = (V,E) and an integer k, whether there exists (bâ,,â¦ ,b_{k-1}) â^^ V^{k} such that every vertex in G has distance at most i from some b_i. This problem is known to be NP-complete even on connected caterpillars of maximum degree 3. We study the parameterized complexity of this problem and answer all questions arose by Kare and Reddy [IWOCA 2019] about parameterized complexity of the problem. We show that the problem is W[2]-complete parameterized by k and that it does not admit a polynomial kernel parameterized by vertex cover number unless NP âS coNP/poly. We also show that the problem is fixed-parameter tractable parameterized by clique-width plus the maximum diameter among all connected components. This implies the fixed-parameter tractability parameterized by modular-width, by treedepth, and by distance to cographs. Although the parameterization by distance to split graphs cannot be handled with the clique-width argument, we show that this is also tractable by a reduction to a generalized problem with a smaller solution size.
关键词：Graph burning; parameterized complexity; fixed-parameter tractability