论文标题
阈值阈值限制为$ 0 $，$ 1 $和顶点学位
Non-monotone target sets for threshold values restricted to $0$, $1$, and the vertex degree
论文作者
论文摘要
我们考虑一个非单向激活过程$（x_t）_ {t \ in \ {0,1,2，\ ldots \}} $在图$ g $上，其中$ x_0 \ subseteq v（g）$，$ x_t = \ \ \ \ \ \ \ \ \ \ \ \ \ \ e \ g ge n_g（g） τ（u）\} $对于每个正整数$ t $，$τ：v（g）\ to \ mathbb {z} $都是阈值函数。设置$ x_0 $是如果有一些$ t_0 $，则为$（g，τ）$的所谓的非占用目标集，以便每$ x_t = v（g）$每$ t \ geq t_0 $。 Ben-Zwi，Hermelin，Lokshtanov和Newman [离散优化8（2011）87-96]询问，如果$ G $是一棵树，是否可以有效地确定目标最低订单。我们在\ {0,1，d_g（u）\} $中满足$τ（u）\满足的阈值函数的肯定问题$τ$。对于此类限制的阈值函数，我们给出了目标集的表征，以表明最小目标设置问题仍然是最高度$ 3 $的平面图的NP-螺态，但对于有界树宽的图表可有效解决。
We consider a non-monotone activation process $(X_t)_{t\in\{ 0,1,2,\ldots\}}$ on a graph $G$, where $X_0\subseteq V(G)$, $X_t=\{ u\in V(G):|N_G(u)\cap X_{t-1}|\geq τ(u)\}$ for every positive integer $t$, and $τ:V(G)\to \mathbb{Z}$ is a threshold function. The set $X_0$ is a so-called non-monotone target set for $(G,τ)$ if there is some $t_0$ such that $X_t=V(G)$ for every $t\geq t_0$. Ben-Zwi, Hermelin, Lokshtanov, and Newman [Discrete Optimization 8 (2011) 87-96] asked whether a target set of minimum order can be determined efficiently if $G$ is a tree. We answer their question in the affirmative for threshold functions $τ$ satisfying $τ(u)\in \{ 0,1,d_G(u)\}$ for every vertex~$u$. For such restricted threshold functions, we give a characterization of target sets that allows to show that the minimum target set problem remains NP-hard for planar graphs of maximum degree $3$ but is efficiently solvable for graphs of bounded treewidth.
