2020/07/10 by Lucas Keiler, Keiler, Lucas, Carlos Vinicius G. C. Lima +7 · 1 citation
Computer Science · Mathematics · #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2007.05246
openalex publication_date 2020/07/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A target set selection model is a graph G with a threshold function τ:V→ ℕ upper-bounded by the vertex degree. For a given model, a set S0⊆ V(G) is a target set if V(G) can be partitioned into non-empty subsets S0,S1,\dotsc,St such that, for i ∈ \1, …, t\, Si contains exactly every vertex v having at least τ(v) neighbors in S0∪…∪ Si-1. We say that t is the activation time tτ(S0) of the target set S0. 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 S0 that maximizes tτ(S0). 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 S0 such that tτ(S0)≥ k. Let τ^* = maxv ∈ 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 τ⋆; otherwise, it is NP-complete even for fixed k=4 and τ⋆=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 S0 in a given tree maximizing tτ(S0).