# Multi-Winner Election Control via Social Influence: Hardness and Algorithms for Restricted Cases
## 4 Multi-Winner Election Control on Graph under LTM  
It is proven that the problem is _NP_-hard to approximate within any factor of approximation using ICM [9]. In this part, we prove the same statement considering LTM. Theorem 4.1: _It is NP-hard to approximate CMV and CDW within any factor on a given graph under LTM._  
Proof: Let us reduce the vertex cover (VC) problem to any approximation algorithm for CDW (reps., CMV). In VC, we are given an undirected graph \(G=(V,E)\) and an integer \(k\); the decision question is: Is there a set of nodes \(V^{\prime}\subseteq V\) (\(|V^{\prime}|\leqslant k\)) so that for each edge \((u,v)\in E\), at least one of its vertices are in \(V^{\prime}\)? Assume \(\mathcal{I}(G,B)\) is a given instance for VC problem, where \(G=(V,E)\) is the given graph, and \(B\) is an integer value. We create an instance \(\mathcal{I}^{\prime}(G^{\prime},B)\) for CDW (reps., CMV) so that \(G^{\prime}=(V\cup V^{\prime}\cup V^{\prime\prime},E^{\prime})\) is the graph build from \(G\), and \(B\) is also the budget for our problem. Let us consider a case where there are two parties and four candidates, i.e., \(t=k=2,C=C_{1}\cup C_{2}\), \(C_{1}=\{c_{1}^{1},c_{2}^{1}\},C_{2}=\{c_{2}^{1},c_{2}^{2}\}\). We fix the order of candidates in the probability distribution of the voter \(v\) as \(\pi_{v}=(\pi_{v}(c_{1}^{1}),\pi_{v}(c_{2}^{1}),\pi_{v}(c_{1}^{2}),\pi_{v}(c_{2}^ {2}))\), and build \(G^{\prime}\) as follows. * For each undirected edge \((u,v)\in E\) add two directed edges \((u,v),(v,u)\) to \(E^{\prime}\). Set the weight of each incoming edge to a node \(v\in V\) as \(\frac{1}{|N_{v}|}\). By this the sum over weight of all incoming edges is equal to one, i.e., \(\forall v\in V:\sum_{u\in N_{v}}b_{u,v}=1\). * For each node \(v\in V\), add two more nodes \(v^{\prime},v^{\prime\prime}\) to \(V^{\prime},V^{\prime\prime}\), respectively. Furthermore, add an edge \((v,v^{\prime})\) to \(E^{\prime}\) with \(b_{v,v^{\prime}}=1\). Formally, \(\forall v\in V:v^{\prime}\in V^{\prime},v^{\prime\prime}\in V^{\prime\prime},(v,v^{\prime})\in E^{\prime}\) s.t. \(b_{v,v^{\prime}}=1\). Note that nodes in \(V^{\prime\prime}\) are isolated. * Set the preferences list of the nodes as follows. \[\forall v\in V,\pi_{v} =(\frac{1}{2},\frac{1}{2},0,0),\] \[\forall v^{\prime}\in V^{\prime},\pi_{v^{\prime}} =(\frac{1}{2},0,\frac{1}{2},0),\] \[\forall v^{\prime\prime}\in V^{\prime\prime},\pi_{v^{\prime \prime}} =(0,0,\frac{1}{2},\frac{1}{2}).\]  
By this reduction, the score of candidates before any diffusion is \(\mathcal{F}(c_{1}^{1},\mathcal{O})=\mathcal{F}(c_{1}^{2},\mathcal{O})=|V|\), \(\mathcal{F}(c_{2}^{1},\mathcal{O})=\mathcal{F}(c_{2}^{2},\mathcal{O})=\frac{1 }{2}|V|\). Then \(F(C_{1},\mathcal{O})=\mathcal{F}(C_{2},\mathcal{O})=1\). Note that in this reduction a node \(v\) will become active deterministically, if either it is selected as a seed node, or all of its incoming neighbors are selected as the seed nodes. Then if we can find a set of seed nodes \(S\subseteq V\) so that it activates all nodes in \(V\) deterministically, the seed set \(S\) is also an answer for the corresponding VC problem. In any approximation algorithm, we know that \(S\subseteq V\) after the diffusion; otherwise, if there is a node \(v^{\prime}\in V^{\prime}\cap S\) we can replace it with its incoming neighbor \(v\in V\) such that \((v,v^{\prime})\in E^{\prime}\) and we get at least the same value for \(\text{MoV}_{c},\text{DoW}_{c}\). Furthermore, if there exists a node \(v^{\prime\prime}\in V^{\prime\prime}\cap S\) one of the following situations holds:  
* There exists an inactive node \(v\in V\setminus A_{S}\) after the diffusion \(S\). In this case, we can substitute \(v\) for \(v^{\prime\prime}\) and then we get at least the same \(\text{DoW}_{c},\text{MoV}_{c}\). * There is no inactive node \(v\in V\setminus A_{S}\). In this case, according to the nodes' probability distribution, when all nodes in \(V\) become active, the value of \(\text{MoV}_{c}\) and \(\text{DoW}_{c}\) is maximum.