论文标题
k燃烧数量问题的APX硬度和近似
APX-Hardness and Approximation for the k-Burning Number Problem
论文作者
论文摘要
考虑以$ k> 0 $ burnt顶点开头的图$ g $上的信息扩散过程，在随后的每个步骤中，都燃烧了当前燃烧的顶点的邻居，以及$ k $其他未燃烧的顶点。 $ g $的\ emph {$ k $燃烧的数字}是最小步骤$ b_k（g）$的最小数量，因此所有顶点都可以在$ b_k（g）$ steps中燃烧。请注意，最后一步可能有大于$ k $未燃烧的顶点，所有这些顶点都被燃烧。 $ 1 $燃烧的数字与众所周知的燃烧数字问题一致，该问题旨在模拟社会传染的传播。对$ k $燃烧的数字的概括使我们能够通过改变点差因子$ k $来检查不同的最坏情况。 在本文中，我们证明，对于任何固定的常数$ k $，计算$ k $燃烧的数字都是apx-hard。然后，我们给出一个$ o（（（n+m）\ log n）$ - 时间3- time 3-AppRoximation算法用于计算$ k $ - 燃烧数量，对于任何$ k \ ge 1 $，其中$ n $和$ m $是顶点和边的数量。最后，我们表明，即使给出燃烧的来源作为输入，计算燃烧序列本身也是NP硬性问题。
Consider an information diffusion process on a graph $G$ that starts with $k>0$ burnt vertices, and at each subsequent step, burns the neighbors of the currently burnt vertices, as well as $k$ other unburnt vertices. The \emph{$k$-burning number} of $G$ is the minimum number of steps $b_k(G)$ such that all the vertices can be burned within $b_k(G)$ steps. Note that the last step may have smaller than $k$ unburnt vertices available, where all of them are burned. The $1$-burning number coincides with the well-known burning number problem, which was proposed to model the spread of social contagion. The generalization to $k$-burning number allows us to examine different worst-case contagion scenarios by varying the spread factor $k$. In this paper we prove that computing $k$-burning number is APX-hard, for any fixed constant $k$. We then give an $O((n+m)\log n)$-time 3-approximation algorithm for computing $k$-burning number, for any $k\ge 1$, where $n$ and $m$ are the number of vertices and edges, respectively. Finally, we show that even if the burning sources are given as an input, computing a burning sequence itself is an NP-hard problem.
