On the complexity of reasoning about opinion diffusion under majority dynamics (Q785234)

This paper studies complexity analysis of opinion diffusion problems under majority dynamics in social networks. A key problems studied in this paper is consensus problem. Given a graph \(G=(N,E)\) and a rational number \(\alpha\) such that \(\alpha\in(0,1)\), this problem requires to compute a set \(S\subseteq N\) of seeds such that \(|S|\le\alpha|N|\) and there is a dynamic \(c\) tends to \(1\) with \(N_{1/c}=S\) or check that there is no set of seeds satisfying the above conditions. Here \(N_{1/c}\) is the set of nodes with opinion \(1\) under a given configuration \(c:N\rightarrow\{0,1\}\). It is shown that consensus problem is a NP-hard problem. Two other problems called double problem and plural problem are also proved to be NP-hard. Double problem refers to computing a configuration \(c\) such that \(|N_{1/c}|\le\varepsilon|N|\) and there exists a dynamic \(c\) tending to \(c^*\) with \(|N_{1/c^*}|>2\varepsilon |N|\) or check that there is no such configuration satisfying the above conditions. Plural problem refers to computing a configuration \(c\) such that \(c\) is stable and \(N_{0/c}\not=\emptyset\) and \(N_{0/c}\not=N\) or check that there is no configuration satisfying the above conditions.