论文标题
图燃烧的参数化复杂性
Parameterized Complexity of Graph Burning
论文作者
论文摘要
图形燃烧问，给定图形$ g =（v，e）$和一个整数$ k $，是否存在$（b_ {0}，\ dots，b_ {k-1}）\ in v^{k} $，以使$ g $中的每个顶点最多都有$ i $ c。即使在最高学位的连接毛毛虫上，该问题也是NP填充的$ 3 $。我们研究了此问题的参数化复杂性，并回答了Kare和Reddy [Iwoca 2019]关于该问题的参数复杂性的所有问题。我们表明，问题是由$ k $进行参数化的W [2] - 整体参数，除非$ \ Mathrm {np} \ subseteq \ mathrm {conp/poly} $，否则它不允许由顶点覆盖号码进行参数化的多项式内核。我们还表明，该问题是固定参数可通过clique tidth进行参数的处理，以及所有连接的组件之间的最大直径。这意味着通过模块化宽度，Treedeptth和距Cographs参数化的固定参数障碍性。尽管无法使用clique宽度参数来处理距离分开图的参数化，但我们表明，这也可以通过减少到较小的解决方案大小的广义问题来处理。
Graph Burning asks, given a graph $G = (V,E)$ and an integer $k$, whether there exists $(b_{0},\dots,b_{k-1}) \in 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 no admit a polynomial kernel parameterized by vertex cover number unless $\mathrm{NP} \subseteq \mathrm{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.
