Target set selection with maximum activation time - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
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.66 Ko) 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, 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⟩
12 View
24 Download

Altmetric

Share

More