# Adding Edges for Maximizing Weighted Reachability +
## 3 Hardness Results
The MC problem is defined as follows: given a ground set of items \(X=\{x_{1},\ldots,x_{n}\}\), a collection of subsets \(F=\{S_{1},\ldots,S_{m}\}\) of subsets of \(X\), and an integer \(k\), find \(k\) sets in \(\mathcal{F}\) that maximise the cardinality of their union. We first focus on the single sink problem. Given an instance of the MC problem \(I_{\text{MC}}=(X,F,k)\), we define an instance of the (maximisation) MCI problem \(I_{MCI}=(G,k)\) similar to the one used in Theorem 1, but where we modify the weights and add \(Y\) paths of one node between each \(v_{x_{j}}\) and \(v\), where \(Y\) is an arbitrarily high number (polynomial in \(n+m\)). In detail, \(I_{MCI}\) is defined 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_{x_{j}}^{l}|x_{j} \in X\text{ and }l=1,\ldots,Y\}\cup\{v\}\) and \(E=\{(v_{S_{i}},v_{x_{j}})|x_{j}\in S_{i}\}\cup\{(v_{x_{j}},v_{x_{j}}^{l})|x_{j }\in X,l=1,\ldots,Y\}\cup\{(v_{x_{j}}^{l},v)|x_{j}\in X,l=1,\ldots,Y\}\);
* \(w(v)=1\) and \(w(u)=0\), for each \(u\in V\setminus\{v\}\); and
* \(p_{v}=1\) for any node \(v\in V\). See Figure 1 (right, top) for an example. We first show that there exists a solution \(F^{\prime}\subseteq F\) to \(I_{\text{MC}}\) that covers \(n^{\prime}\) elements of \(X\) if and only if there exists a solution \(S\) to \(I_{MCI}\) such that \(f(S)=n^{\prime}(Y+1)+B+1\). Moreover, we can compute \(F^{\prime}\) from \(S\) and vice versa in polynomial time. Indeed, given \(F^{\prime}\), we define \(S\) as \(S=\{(v,v_{S_{j}})|S_{i}\in F^{\prime}\}\). We can verify that \(f(S)=n^{\prime}(Y+1)+B+1\) and \(|S|=k=B\). Indeed, only node \(v\) as a weight different from \(0\), and then \(f(S)=R(v,S)=n^{\prime}(Y+1)+B+1\), since \(v\) can reach the \(n^{\prime}(Y+1)\) nodes \(v_{x_{j}}\) corresponding to the items \(x_{j}\) covered by \(F^{\prime}\), the \(B\) nodes \(v_{S_{i}}\) it is connected to, and itself. On the other hand, given a solution \(S\) to \(I_{MCI}\), by Lemma 2, we can assume that it has only edges from \(v\) to nodes \(v_{S_{i}}\). Let \(n^{\prime}\) be the number of nodes \(v_{x_{j}}\) in \(R(v,S)\), then \(f(S)=n^{\prime}(Y+1)+B+1\) and \(F^{\prime}=\{S_{i}|(v,v_{S_{i}})\in S\}\) covers \(n^{\prime}\) elements in \(X\). If \(OPT(I_{\text{MC}})\) and \(OPT(I_{MCI})\) denote the optimum value for \(I_{\text{MC}}\) and \(I_{MCI}\), respectively, then \(OPT(I_{\text{MCI}})\geq OPT(I_{\text{MC}})(Y+1)+B+1\geq Y\cdot OPT(I_{\text{ MC}})\). Moreover, given the above definition of \(S\) and \(F^{\prime}\), then for any \(\epsilon^{\prime}>0\) there exists a value of \(Y=\mathcal{O}(poly(n+m))\) such that \(f(S)\leq(n^{\prime}+\epsilon^{\prime})Y\). Let us assume that there exists a polynomial-time algorithm that guarantees an \(\alpha\) approximation for \(I_{\text{MCI}}\), then we can compute a solution \(S\) such that \(f(S)\geq\alpha OPT(I_{MCI})\). It follows that:  
\[\alpha Y\cdot OPT(I_{\text{MC}})\leq\alpha OPT(I_{MCI})\leq f(S)\leq(n^{ \prime}+\epsilon^{\prime})Y,\]  
where \(n^{\prime}\) is the number of nodes covered by the solution \(F^{\prime}\) to MC obtained from \(S\). Therefore, we obtain an algorithm that approximates the MC problem with a factor \(\alpha\) (up to lower order terms). Since it is \(NP\)-hard to approximate to within a factor greater than \(1-\frac{1}{e}\)[26], then the statement follows. Let us now focus on the single source case. Given \(I_{\text{MC}}\), we define \(I_{MCI}=(G,B)\) 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\}\cup\{v^{ \prime}|l=1,\ldots Y\}\) and \(E=\{(v_{x_{j}},v_{S_{i}})|x_{j}\in S_{i}\}\cup\{(v,v_{x_{j}})|x_{j}\in X\}\cup\{( v,v^{\prime})|l=1,\ldots Y\}\);
* \(w(v_{x_{j}})=1\), for each \(x_{j}\in X\) and \(w(u)=0\), for each \(u\in V\setminus\{v_{x_{j}}|x_{j}\in X\}\); and
* \(p_{v}=1\) for any node \(v\in V\). \(Y\) is an arbitrarily high polynomial value in \(m+n\). See Figure 1 (right, bottom) for an example. We use similar arguments as above.