Search

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 S 0 ⊆ V(G) is a target set if V (G) can be partitioned into non-empty subsets S 0 , S 1 ,....,S t such that, for all i∈{1,....,t}, S i contains exactly every vertex v having at least τ(v) neighbors in S 0 ∪⋯∪S i−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 S 0 such that t τ (S 0)≥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 τ (S 0). [ABSTRACT FROM AUTHOR]

In the Red–Blue Dominating Set problem, we are given a bipartite graph G = ( V B ∪ V R , E ) and an integer k , and asked whether G has a subset D ⊆ V B of at most k “blue” vertices such that each “red” vertex from V R is adjacent to a vertex in D . We provide the first explicit linear kernel for this problem on planar graphs, of size at most 43 k . [ABSTRACT FROM AUTHOR]

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 S 0 ⊆ V (G) is a target set if V (G) can be partitioned into non-empty subsets S 0 , S 1 , ... , S t such that, for all i ∈ { 1 , ... , t } , S i contains exactly every vertex v outside S 0 ∪ ⋯ ∪ S i − 1 having at least τ (v) neighbors in S 0 ∪ ⋯ ∪ 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) ≥ 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 S 0 in a given tree maximizing t τ (S 0). [ABSTRACT FROM AUTHOR]