Pervasive Domination

Inspired by the implicit or explicit persuasion scenario, which characterizes social media platforms, we analyze a novel domination problem named Pervasive Partial Domination (PPD). We consider a social network modeled by a digraph G= (V, E) where an arc (u, v) ∈ E represents the capability of an individual u to persuade an individual v. We are looking for a set S⊂ V of social change individuals, of minimum cost, who combined enable to reach the desired behavior. The impact of S is measured by a set function f(S) that is the sum of the degree of belief of all the individuals in the network and p is the desired target. We show that the natural greedy algorithm, for the PPD problem, provides an approximation guarantee, (lnp-f(∅)β+2) where β> 0 represents the minimum gain on the function f one can attain by bribing an additional individual when the target p is (almost) reached. The proposed solution can be generalized to the weighted partial sumbmodular cover problem providing a better approximation with respect to the state of the art.