Target set selection with maximum activation time

Abstract

A target set selection model is a graph $G$ with a threshold function $\tau :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,\dots ,S_t$ such that, for $i\in \{1,\dots ,t\}$, $S_i$ contains exactly every vertex $v$ having at least $\tau (v)$ neighbors in $S_0\cup \cdots \cup S_{i-1}$. We say that $t$ is the activation time $t_{\tau }(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_{\tau }(S_0)$. That is, given a graph $G$, a threshold function $\tau$ 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_{\tau }(S_0)\ge k$. Let ${\tau }^{\ast }={\max }_{v\in V(G)}\tau (v)$. Our main result is the following dichotomy about the complexity of TSS-time when $G$ belongs to a minor-closed graph class $\mathcal{C}$: if $\mathcal{C}$ has bounded local treewidth, the problem is FPT parameterized by $k$ and ${\tau }^{\star }$; otherwise, it is NP-complete even for fixed $k=4$ and ${\tau }^{\star }=2$. We also prove that, with ${\tau }^{\ast }=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_{\tau }(S_0)$.

27 pages, 12 figures