Exact solutions for Latency-Bounded Target Set Selection Problem on some special families of graphs

In the tt-Latency-Bounded Target Set Selection (tt-LBTSS) problem, we are given a simple graph G=(V,E)G=(V,E), a certain latency bound tt and a threshold function θ(v)=⌈ρd(v)⌉θ(v)=⌈ρd(v)⌉ for every vertex vv of GG, where 0<ρ<10<ρ<1 is a rational number and d(v)d(v) is the degree of vv in VV, the goal is to find a target set SS with smallest cardinality such that all vertices in VV are activated by SS by a so called “diffusion process” within tt rounds as follows: Initially, all vertices in the target set become activate. Then at each step ii of the process, each vertex get activated if the number of active vertices in its neighbor after i−1i−1 exceeds its threshold.For general graphs, the tt-LBTSS problem is not only NP-hard, it is also hard to be approximated by Chen’s inapproachability results (Chen, 2009). In this paper, we are interested in finding an optimal target set for some special family of graphs. A simple, tight but nontrivial inequality was presented which gives the lower bound of the total sum of degrees in a feasible target set to tt-LBTSS problem, in terms of the number of edges in the graph. Necessary and sufficient conditions for equality to hold have been established, based on which we are able to construct families of infinite number of graphs for which the optimal solution to tt-LBTSS problem become obvious. In particular, we gave an exact formula for the optimal solution of a kind of toroidal mesh graphs, while it seems difficult to tell what the optimal solutions are for these graphs without using the equality given in the paper.