论文标题
目标集选择随着最大激活时间
Target set selection with maximum activation time
论文作者
论文摘要
目标集选择模型是具有阈值函数$τ：v \ to \ mathbb {n} $上限由顶点度数的图形$ g $。对于给定型号，如果可以将$ v（g）$的$ s_0 \ subseteq v（g）$分配为目标集，则可以将$ s_0，s_1，\ dotsc，s_t $分配到非空的子集中$ s_0 \ cup \ dots \ cup s_ {i-1} $中的邻居。我们说$ t $是目标设置$ s_0 $的激活时间$t_τ（s_0）$。在这种模型的情况下，发现最小尺寸的目标集的问题已在文献中进行了广泛的研究。在本文中，我们调查了其称为TSS时间的变体，其中的目标是找到一个目标集$ s_0 $，该$ s_0 $最大化$t_τ（s_0）$。也就是说，给定图形$ g $，$ g $中的阈值函数$τ$和一个整数$ k $，tss时间问题的目的是决定$ g $是否包含目标集$ s_0 $，因此$t_T_τ（s_0）\ geq k $。令$τ^* = \ max_ {v \ in V（g）}τ（v）$。我们的主要结果是二分法是关于$ g $属于少量封闭的图级$ {\ cal c} $的复杂性的二分法：如果$ {\ cal c} $具有限制的本地树，则问题是由$ k $ and $ k $和$ k $ and $τ^{\ star} $ f.否则，即使对于固定的$ k = 4 $和$τ^{\ star} = 2 $，它即使是固定的$ k = 4 $也是np完整的。我们还证明，使用$τ^*= 2 $，问题是固定$ k = 5 $的两分图中的np-hard，从以前的结果中，我们观察到TSS时间在平面图中是NP-HARD，W [1] - 由TreeWidth参数化。最后，我们提出了一种线性时间算法，以在给定的树中找到目标集$ s_0 $，以最大化$t_τ（s_0）$。
A target set selection model is a graph $G$ with a threshold function $τ:V\to \mathbb{N}$ upper-bounded by the vertex degree. For a given model, a set $S_0\subseteq V(G)$ is a target set if $V(G)$ can be partitioned into non-empty subsets $S_0,S_1,\dotsc,S_t$ such that, for $i \in \{1, \ldots, t\}$, $S_i$ contains exactly every vertex $v$ having at least $τ(v)$ neighbors in $S_0\cup\dots\cup S_{i-1}$. We say that $t$ is the activation time $t_τ(S_0)$ of the target set $S_0$. The problem of, given such a model, finding a target set of minimum size has been extensively studied in the literature. In this article, we investigate its variant, which we call TSS-time, in which the goal is to find a target set $S_0$ that maximizes $t_τ(S_0)$. That is, given a graph $G$, a threshold function $τ$ in $G$, and an integer $k$, the objective of the TSS-time problem is to decide whether $G$ contains a target set $S_0$ such that $t_τ(S_0)\geq k$. Let $τ^* = \max_{v \in V(G)} τ(v)$. Our main result is the following dichotomy about the complexity of TSS-time when $G$ belongs to a minor-closed graph class ${\cal C}$: if ${\cal C}$ has bounded local treewidth, the problem is FPT parameterized by $k$ and $τ^{\star}$; otherwise, it is NP-complete even for fixed $k=4$ and $τ^{\star}=2$. We also prove that, with $τ^*=2$, the problem is NP-hard in bipartite graphs for fixed $k=5$, and from previous results we observe that TSS-time is NP-hard in planar graphs and W[1]-hard parameterized by treewidth. Finally, we present a linear-time algorithm to find a target set $S_0$ in a given tree maximizing $t_τ(S_0)$.
