# Adding Edges for Maximizing Weighted Reachability +
## 3 Hardness Results  
In this section, we first show that the MCI problem is _NP_-complete, even in the case in which all the weights and profits are unitary and the graph contains a single sink node or a single source node. Then, we show that it is _NP_-hard to approximate MCI to within a factor greater than \(1-\frac{1}{e}\). This last result holds also in the case of graphs with a single sink node or a single source node, but not in the case of unitary weights. Theorem 3.1: _MCI is NP-complete, even in the case in which all the weights and profits are unitary and the graph contains a single sink node or a single source node._  
Proof: We consider the decision version of MCI in which all the weights and profits are unitary (i.e., \(w_{v}=p_{v}=1\)): Given a directed graph \(G=(V,E)\) and two integers \(M,B\in\mathbb{N}_{\geq 0}\), the goal is to find a set of additional edges \(S\subseteq(V\times V)\setminus E\) such that \(f(S)\geq M\) and \(|S|=B\). The problem is in _NP_ since it can be checked in polynomial time if a set of nodes \(S\) is such that \(f(S)\geq M\) and \(|S|=B\). We reduce from the Set Cover (SC) problem which is known to be _NP_-complete [25]. Consider an instance of the SC problem \(I_{SC}=(X,F,k)\) defined by a collection of subsets \(F=\{S_{1},\ldots,S_{m}\}\) for a ground set of items \(X=\{x_{1},\ldots,x_{n}\}\). The problem is to decide whether there exist \(k\) subsets whose union is equal to \(X\). We define a corresponding instance \(I_{MCI}=(G,M,B)\) of MCI as follows:  
* \(B=k\);
* \(G=(V,E)\), where \(V=\{v_{x_{j}}|x_{j}\in X\}\cup\{v_{S_{i}}|S_{i}\in F\}\cup\{v\}\) and \(E=\{(v_{S_{i}},v_{x_{j}})|x_{j}\in S_{i}\}\cup\{(v_{x_{j}},v)|x_{j}\in X\}\); and
* \(M=(n+1+B)^{2}+(m-B)(n+B+2)\). See Figure 1 (left, top) for an example. Note that \(G\) is a DAG. By Lemma 2, we can assume that any solution \(S\) of MCI contains only edges \((v,v_{S_{i}})\) for some \(S_{i}\in F\). In fact, \(v\) is the only sink node and \(v_{S_{i}}\) are the only source nodes. Assume that there exists a set cover \(F^{\prime}\); then, we define a solution \(S\) to the MCI instance as \(S=\{(v,v_{S_{i}})|S_{i}\in F^{\prime}\}\). It is easy to show that \(f(S)=M\) and \(|S|=k=B\). Indeed, all the nodes in \(G\) can reach: node \(v\), all the nodes \(v_{x_{j}}\) (since \(F^{\prime}\) is a set cover), and all the nodes \(v_{S_{i}}\) such that \(S_{i}\in F^{\prime}\). Moreover, each node \(v_{S_{i}}\) such that \(S_{i}\
ot\in F^{\prime}\) can reach itself. Therefore, there are \(n+B+1\) nodes that reach \(n+B+1\) nodes and \(m-B\) that reach \(n+B+2\) nodes, that is \(f(S)=M\). On the other hand, assume that there exists a solution for MCI; then, \(S\) is in the form \(\{(v,v_{S_{i}})|S_{i}\in F\}\) and we define a solution for the set cover as \(F^{\prime}=\{S_{i}|(v,v_{S_{i}})\in S\}\). We show that \(F^{\prime}\) is a set cover. By contradiction, if we assume that \(F^{\prime}\) is not a set cover and it cover only \(n^{\prime}<n\) elements of \(X\), then \(f(S)=(n^{\prime}+B+1)^{2}+(n-n^{\prime}+m-B)(n^{\prime}+B+2)<M\). Note that, in the above reduction, the graph \(G\) has a single sink node. We can prove the _NP_-hardness of the case of graphs with a single source node by using the same arguments on an instance of MCI made of the inverse graph of \(G\), \(M=(B+n+1)(n+m+1)+m-B\), and \(B=k\) (see Figure 1 (left, bottom) for an example). Theorem 3.2: _MCI is NP-hard to approximate to within a factor \(1-\frac{1}{e}+\epsilon\), for any \(\epsilon>0\), even if graph contains a single sink node or a single source node._  
Figure 1: Examples of reductions used in Theorems 2.1 and 2. Proof. : We give two approximation factor preserving reductions from the Maximum Coverage problem (MC), which is known to be \(NP\)-hard to approximate to within a factor greater than \(1-\frac{1}{e}\)[26].