Balancing the Spread of Two Opinions in Sparse Social Networks (Student Abstract)

Abstract

We propose a new discrete model for simultaneously spreading two opinions within a social network inspired by the famous Target Set Selection problem. We are given a social network, a seed-set of agents for each opinion, and two thresholds per agent. The first threshold represents the willingness of an agent to adopt an opinion if she has no opinion at all, while the second threshold states the readiness to acquire a second opinion. The goal is to add as few agents as possible to the initial seed-sets such that, once the process started with these seed-set stabilises, each agent has either both opinions or none. We perform an initial study of its computational complexity. It is not surprising that the problem is NP-hard even in quite restricted settings. Therefore, we investigate the complexity of the problem from the parameterized point-of-view with special focus on sparse networks, which appears often in practice. Among other things, we show that the proposed problem is in the FPT complexity class if we parameterize by the vertex cover number of the underlying graph.