# Multi-Winner Election Control via Social Influence: Hardness and Algorithms for Restricted Cases
## 5 Multi-Winner Election Control on Arborescence under ICM  
In this section, instead of a general graph, we consider an arborescence structure. We are given a tree \(G=(V,E)\) and a budget \(B\) where the directed edges are from leaves towards the root under ICM. We are asked to find at most \(B\) seed nodes to maximize \(\mathrm{MoV}_{c}\) and \(\mathrm{DoW}_{c}\). It has been shown that the problem in inapproximable on a general graph, except \(P=NP\)[9]. [PERSON] et al. conjectured that the IM problem considering ICM on arborescence is \(NP\)-hard [26]. [PERSON] et al. proved that the conjecture is true [27], while [PERSON] et al. showed that the IM problem accepts a polynomial-time algorithm on arborescence under LTM [28]. In the following, we show that our problem is hard to approximate within any factor of approximation on arborescence under ICM. It is NP-hard to find an approximation algorithm for CMV and CDW on arborescence under ICM. Proof. : We show the hardness by reducing the IM problem to our problem. Given an instance \(\mathcal{I}(T,B)\) of IM problem where \(T=(V,E)\) is the tree (arborescence), and \(B\) is the budget. Let us define the decision version of the problem as follows: is there at most \(B\) seed nodes so that it activates all nodes of the tree in expected? We consider the case where there are two parties and each of them have just two candidates, i.e., \(C=C_{1}\cup C_{2},C_{1}=\{c_{1}^{1},c_{2}^{1}\},C_{2}=\{c_{1}^{2},c_{2}^{2}\}\). Furthermore, for simplicity, we consider the plurality scoring rule. The proof can be extended for any number of parties and candidates using any non-increasing scoring function, akin to [29]. Let us create an instance of our problem \(\mathcal{I}^{\prime}(T^{\prime},B)\) as follows, where \(T^{\prime}=(V\cup V^{\prime}\cup V^{\prime\prime},E)\) is a tree, and \(B\) is the same budget for both problems. * For each node \(v\in V\) we add two more nodes \(v^{\prime},v^{\prime\prime}\) to \(V^{\prime},V^{\prime\prime}\), respectively, i.e., \(\forall v\in V:v^{\prime}\in V^{\prime}\), \(v^{\prime\prime}\in V^{\prime\prime}\). * For each node \(v\in V\) we add an edge \((v,v^{\prime\prime})\) to \(E\) where \(b_{v,v^{\prime\prime}}=1\). * Set the preference list of all nodes as follows. \[\forall v\in V:c_{1}^{2}\succ c_{2}^{2}\succ c_{1}^{1}\succ c_{2}^ {1},\] \[\forall v^{\prime}\in V^{\prime}:c_{2}^{2}\succ c_{1}^{2}\succ c _{2}^{1}\succ c_{1}^{1},\] \[\forall v^{\prime\prime}\in V^{\prime\prime}:c_{1}^{2}\succ c_{1} ^{1}\succ c_{2}^{1}\succ c_{2}^{2}\]  
Clearly, seed nodes will be selected from \(V\), i.e., \(S\subseteq V\); otherwise, if there is a node \(v^{\prime}\in S\cap V^{\prime}\), then the node is useless and does not affect \(\mathrm{DoW}_{c}\) or \(\mathrm{MoV}_{c}\). If there is a node \(v^{\prime\prime}\in S\cap V^{\prime\prime}\), we can replace it with its incoming neighbor and get at least the same value for \(\mathrm{DoW}_{c}\) and \(\mathrm{MoV}_{c}\). Using aforementioned polynomial-time reduction, if there exists a set of nodes \(S\subseteq V\) (\(|S|\leqslant B\)) so that \(\mathrm{MoV}_{c}>0\) (resp. \(\mathrm{DoV}_{c}>0\)), then the node will activate all nodes in \(V\cup V^{\prime\prime}\). Hence, we can select the same set and they will activate all nodes in \(T\); then the answer of \(\mathcal{I}\) will be YES. On the other hand, if \(\mathrm{MoV}_{c}=0\) (resp. \(\mathrm{DoW}_{c}=0\)), it means there is no seed set can activate all nodes in \(V\cup V^{\prime\prime}\); then the answer of \(\mathcal{I}\) is NO. More formally, before any diffusion the score of candidates is  
\[\mathcal{F}(c_{1}^{1},\mathcal{O}) =\mathcal{F}(c_{2}^{1},\mathcal{O})=0,\] \[\mathcal{F}(c_{1}^{2},\mathcal{O}) =2|V|,\] \[\mathcal{F}(c_{2}^{2},\mathcal{O}) =|V|.\]Then, none of the candidates in our target party will be elected as winner.