On the complexity of opinion consensus under majority dynamics

Opinion diffusion is studied on social graphs where agents hold opinions and where social pressure leads them to conform to the opinion manifested by the majority of their neighbors. Within this setting, questions related to which extent a minority/majority can spread the opinion it supports to the other agents are considered. It is shown that if there are only two available opinions, no matter of the underlying social graph G = (N,E), there is always a group formed by a half of the agents that can annihilate the opposite opinion. A polynomial-time algorithm to compute a group of agents enjoying these properties is also devised and analyzed. The result marks the boundary of tractability, since the influence power of minorities is shown to depend on certain features of the underlying graphs, which are NP-hard to be identified. Finally, for more than two opinions we show that even the simpler problem of deciding whether there exists a sequence of updates leading to consensus is NP-hard.