# Multi-Winner Election Control via Social Influence: Hardness and Algorithms for Restricted Cases
## 4 Multi-Winner Election Control on Graph under LTM
Then even if we remove \(v^{\prime\prime}\) from \(S\) it does not change the value of \(\text{MoV}_{c}\) or \(\text{DoW}_{c}\). By the way, in this situation, if there exist any node \(v\in V\setminus A_{S}\) we replace \(v^{\prime\prime}\) with it, otherwise we replace it with a node \(v\in V\setminus S\). Then from now on, we assume \(S\subseteq V\). If all nodes in \(V\) become active, since they have an outgoing edge to all nodes \(v^{\prime}\in V^{\prime}\) with probability one, then all nodes in \(V\cup V^{\prime}\) will become active, and the score of the candidates will be as follows. \[\mathcal{F}(c_{1}^{1},S) =|V|,\] \[\mathcal{F}(c_{2}^{1},S) =\mathcal{F}(c_{1}^{2},S)=\frac{3}{4}|V|,\] \[\mathcal{F}(c_{2}^{2},S) =\frac{1}{2}|V|.\]  
Then \(F(C_{1},S)=2,\mathcal{F}(C_{2},S)=0\), \(\text{DoW}_{c}(C_{1},S)>0\), \(\text{MoV}_{c}(C_{1},S)>0\), and any approximation algorithm will return a positive value, then the answer of \(\mathcal{I}\) will be YES. On the other hand, if there is a node \(v\in V\), which is inactive after the diffusion, i.e., \(\exists v\in V\setminus A_{S}\), the score of candidates will be as follows. \[\mathcal{F}(c_{1}^{1},S) =|V|,\] \[\mathcal{F}(c_{2}^{1},S) <\frac{3}{4}|V|,\] \[\mathcal{F}(c_{1}^{2},S) >\frac{3}{4}|V|,\] \[\mathcal{F}(c_{2}^{2},S) =\frac{1}{2}|V|.\]  
Then \(F(C_{1},S)=\mathcal{F}(C_{2},S)=1,\text{DoW}_{c}(C_{1},S)=\text{MoV}_{c}(C_{1 },S)=0\), and any approximation algorithm will return zero, then the answer of \(\mathcal{I}\) will be NO. For the other direction, note that if we can find a set of nodes \(S\subseteq V\), which is an answer for \(\mathcal{I}\), using the same set of nodes, we can activate all nodes in \(V\cup V^{\prime}\) and \(\text{DoW}_{c}(C_{1},S)>0\), \(\text{MoV}_{c}(C_{1},S)>0\). To extend the proof for any number of parties (\(t\)) and candidates (\(k\)), we need to assign the probability distribution as follows, and the same approach concludes the proof for any \(t,k>2\). The same as before, the order of the candidates in probability distribution of a voter \(v\) is \(\pi_{v}=(\pi_{v}(c_{1}^{1}),\ldots,\pi_{v}(c_{k}^{1}),\pi_{v}(c_{1}^{2}),\ldots,\pi_{v}(c_{k}^{2}),\ldots,\pi_{v}(c_{1}^{t}),\ldots,\pi_{v}(c_{k}^{t}))\). \[\forall v^{\prime}\in V^{\prime},\pi_{v^{\prime}} =(\frac{1}{2},0,\frac{1}{2},0),\]0 \[\forall v^{\prime}\in V^{\prime},\pi_{v^{\prime}} =(\frac{1}{2},0,\frac{1}{2},0),\]1 \[\forall v^{\prime}\in V^{\prime},\pi_{v^{\prime}} =(\frac{1}{2},0,\frac{1}{2},0),\]2  
The following theorem proves the same statement for the destructive case of the problem. Theorem 4.2: _It is NP-hard to approximate DMV and DDW within any factor on a given graph under LTM._  
Proof. : The reduction is similar to the constructive case. Consider the case where \(t=k=2\). We should set the voters' probability distributions such that one of our target candidates be among the losers before and after any diffusion. Furthermore, another target candidate is among the winners before any dissemination; however, he will lose the election if and only if all nodes in the connected part of the graph become active. Please note that, since our target candidates have more priority than the others, we need one more node to be able to do that.