The complexity of finding harmless individuals in social networks

In this paper, we introduce a domination-related problem called Harmless Set: given a graph  G=(V,E)G=(V,E), a threshold function  t:V→Nt:V→N and an integer  kk, find a subset of vertices  V′⊆VV′⊆V of size at least  kk such that every vertex  vv in  VV has less than  t(v)t(v) neighbors in  V′V′. We study its parameterized complexity and the approximation of the associated maximization problem. When the parameter is  kk, we show that the problem is W[2]-complete in general and W[1]-complete if all thresholds are bounded by a constant. Moreover, we prove that, if  P≠NPP≠NP, the maximization version is not  n12−ε-approximable for any  ε>0ε>0 even when all thresholds are at most two. When each threshold is equal to the degree of the vertex, we show that Harmless Set is fixed-parameter tractable for parameter  kk and the maximization version is APX-complete. We give a polynomial-time algorithm for graphs of bounded treewidth and a polynomial-time approximation scheme for planar graphs. Finally, we show that the parametric dual problem (n−k)(n−k)-Harmless Set is fixed-parameter tractable for a large family of threshold functions.