# Multi-Connectivity for Multicast Video Streaming in Cellular Networks
## 4 Computational Complexity  
We show that the resource allocation problem \(\mathbf{K}^{*}\) is NP-hard, and therefore, no polynomial-time algorithms exist for solving it. We prove this through a reduction from the Maximum Coverage Problem (MCP) [39], which is a known NP-hard problem defined as follows. **Definition 2** (Maximum Coverage Problem (MCP)). : _Consider a universal set \(\mathcal{S}\), a number \(k\in\mathds{N}\), and a collection of sets \(\mathcal{T}=\{T_{1},T_{2},\ldots,T_{m}\}\), where for all \(j\in[m]\), \(T_{j}\subseteq\mathcal{S}\). The objective of the MCP is to determine a sub-collection \(\mathcal{T}^{\prime}\subseteq\mathcal{T}\) such that \(\mathcal{T}^{\prime}\in\operatorname*{arg\,max}_{|\mathcal{T}^{\prime}| \leq k}|\bigcup_{T_{j}\in\mathcal{T}^{\prime}}T_{j}|\)._  
That is, given a collection \(\mathcal{T}\) of \(m\) subsets of a universal set \(\mathcal{S}\), the objective of the MCP is to find the sub-collection of at most \(k\) subsets from \(\mathcal{T}\) that cover the maximum number of elements from the universal set \(\mathcal{S}\). **Theorem 1**. : _The MC multicast resource allocation problem \(\mathbf{K}^{*}\) is NP-hard._  
Proof. : The proof of the NP-hardness of \(\mathbf{K}^{*}\) can be accomplished in the following steps:  
1. First, we show that an instance of a known NP-hard problem (MCP in this case) can be reduced to an instance of \(\mathbf{K}^{*}\) in polynomial time. This means that we can design a polynomial-time algorithm that takes the MCP as input and results in an instance of \(\mathbf{K}^{*}\). 2. Next, we show that a solution of \(\mathbf{K}^{*}\) can be mapped to a corresponding solution for the MCP in polynomial time. 3. Finally, using the results from steps 1 and 2, we prove that no polynomial-time algorithm exists for solving \(\mathbf{K}^{*}\) because such an algorithm would also provide a polynomial-time solution for the MCP, which is known to be NP-hard. We begin by defining an algorithm to reduce an instance of MCP to an instance of \(\mathbf{K}^{*}\) in polynomial time. An instance of MCP can be reduced to an instance of \(\mathbf{K}^{*}\) as follows:  
* Given an instance of the MCP in Definition 2 with the universal set \(\mathcal{S}\), the collection of \(m\) sets \(\mathcal{T}=\{T_{1},T_{2},\ldots,T_{m}\}\) with \(T_{j}\subseteq\mathcal{S}\) and some \(k\in\mathds{N}\). * Define a MC multicast system with the set of UEs \([M]=\mathcal{S}\), number of cells \(C=k\), and the number of PRBs in each cell \(N=m\), and for all \(c\in[C]\), the set \(U_{j_{C}}=T_{j}\). * This defines a resource allocation problem of the form of \(\mathbf{K}^{*}\) in Definition 1. This reduction can be accomplished in constant time (\(\mathcal{O}(C)\)). The pseudo-code of the algorithm for accomplishing this reduction is given in Algorithm 1. This yields a one-to-one correspondence between an instance of MCP and an instance of \(\mathbf{K}^{\star}\), which completes the first step of the proof. We now proceed to show that a solution of the resulting instance of \(\mathbf{K}^{\star}\) can be mapped to a solution of MCP in polynomial time. Let us assume that there exists a polynomial-time algorithm for solving the instance of \(\mathbf{K}^{\star}\) resulting from Algorithm 1 that provides a solution \(\mathcal{U}^{\prime}\). Then, the following hold true by the definition of \(\mathbf{K}^{\star}\):  
* \(|\mathcal{U}^{\prime}|=k\);
* For all \(c\in[k]\), \(|\mathcal{U}^{\prime}\cap\mathcal{U}_{c}|=1\);
* \(\mathcal{U}^{\prime}\) maximizes \(|\bigcup_{U_{j}\in\mathcal{U}^{\prime}}U_{jc}|\). This solution can be mapped to a solution of MCP as follows. Given the MCP in Definition 2, construct the solution set \(\mathcal{T}^{\prime}=\{T_{1},T_{2},\ldots,T_{m}\}\) such that if \(U_{jc}\in\mathcal{U}^{\prime}\), then \(T_{j}\in\mathcal{T}^{\prime}\). Since \(|\mathcal{U}^{\prime}|=k\), it holds that \(|\mathcal{T}^{\prime}|\leq k\). Therefore, by Definition 2, the constructed set \(\mathcal{T}^{\prime}\) is a feasible solution of the MCP.