Journal Articles Discrete Applied Mathematics Year : 2023

Target set selection with maximum activation time

Abstract

A target set selection model is a graph G with a threshold function τ : V (G) → N 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,. .. , St such that, for all i ∈ {1,. .. , t}, Si contains exactly every vertex v outside S0 ∪ • • • ∪ Si−1 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 τ = max v∈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 C: if 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).
Fichier principal
Vignette du fichier
DA12658-R1.pdf (845) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-04140763 , version 1 (26-06-2023)

Identifiers

Cite

Lucas Keiler, Carlos Vinicius Gomes Costa Lima, Ana Karolinna Maia de Oliveira, Rudini Sampaio, Ignasi Sau. Target set selection with maximum activation time. Discrete Applied Mathematics, 2023, 338, pp.199-217. ⟨10.1016/j.dam.2023.06.004⟩. ⟨lirmm-04140763⟩
20 View
32 Download

Altmetric

Share

More