# Select the maximum number of links to satisfy the constraint on each link. How to prove is NP-hard?

Instance: $n$ non-negative real numbers $P_1,\ldots,P_n$, a positive number $k\le n$, and a positive number $\epsilon$.

Question: Is there a subset $S$ of $\{1,\ldots,n\}$ of cardinality $|S|\geq k$ such that

$$\dfrac{P_i}{\epsilon-P_i+\sum_{j\in S}P_j}\geq 1,\text{ for all } i \in S.$$

Can you see a simple, direct reduction from an NP-hard problem?

Note. This problem is studied in wireless communication where the set represents links in a wireless network, the $P_i$ represents the powers and the constraint represent a quality of service guarantee.

I believe a more general problem is proven NP-hard, see for example here, but the reduction is very hard for me.

• If ​ 0 < $\epsilon$ ​ then the denominator will necessarily be strictly positive, in which case that inequality can be simplified. ​ ​ ​ ​ – user12859 Feb 13 '16 at 0:30
• Are you sure it is $\dfrac{P_i}{\epsilon-P_i+\sum_{j\in S}P_j}\geq 1,\text{ for all } i \in S.$ and not $\dfrac{P_i}{\epsilon-P_i+\sum_{j\in S}P_j}\leq 1,\text{ for all } i \in S.$ or something like $\dfrac{P_i}{\epsilon-P_i+\sum_{j\in S}P_j}\geq \lambda,\text{ for all } i \in S.$ – Shreesh Feb 13 '16 at 7:10

This problem can be solved in polynomial time. Therefore, it's likely not NP-hard (unless P = NP).

After a little bit of algebraic manipulation, we find that the condition on $S$ is equivalent to requiring that

$$2 P_i \ge \varepsilon + \sum_{j \in S} P_j \quad \text{for all i \in S}.$$

This, in turn, is equivalent to requiring

$$2 \min \{P_i : i \in S\} \ge \varepsilon + \sum_{j \in S} P_j.$$

For convenience, sort the $P_i$'s into increasing order, so $P_1 \le P_2 \le \dots \le P_n$.

Now one can prove that if there is any set of cardinality $k$ that satisfies this equation, then there's a set of the form $S = \{t,t+1,t+2,\dots,t+k-1\}$ that satisfies this equation, for some $t$. (This can be proven using an exchange argument, swapping pairs of indices as needed and showing that the swap leaves the left-hand side unchanged and only decreases the right-hand side.)

Now you can try all possible values of $t$ and see whether the corresponding set satisfies the condition. There are only $n$ possible values of $t$, so this can certainly be tested in polynomial time. In fact, with clever programming (prefix sums, etc.), you can implement this in $O(n \lg n)$ time, or in $O(n)$ time if the $P_i$'s are already provided in sorted order.

More generally, if you want to find the set $S$ of maximum cardinality that satisfies the equation, such a set will have the form $S=\{t,t+1,t+2,t+3,\dots,u\}$ for some $t,u$. Therefore, you can try all such possibilities and see which has largest cardinality. This too can be done in $O(n \lg n)$ time using appropriate methods (binary search, prefix sums). Alternatively, you can do binary search on $k$, and apply the decision algorithm of the previous paragraph for each candidate value of $k$ to find the largest $k$ for which a solution exists. The running time is again $O(n \lg n)$.

In equation $\dfrac{P_i}{\epsilon-P_i+\sum_{j\in S}P_j}\geq 1,\text{ for all } i \in S.$, and positive $\epsilon > 0$ we can never have $k \geq 2$. Even in the case $k=2$ either $2P_1 < \epsilon + P_1 + P_2$ or $2P_2 < \epsilon + P_1 + P_2$.

And for $k = 1$ every subset is a yes-instance for small enough $\epsilon$.

So the problem is trivially polynomial.

• Thank you for your comments. If there is $\lambda$ as you said in the definition of the problem, can you see how it is NP-hard? – Chiba Feb 13 '16 at 10:57
• No, it seems it will be in $P$. – Shreesh Feb 13 '16 at 11:35
• The statement "Even in the case $k=2$ either $2P_1<\epsilon+P_1+P_2$ or $2P_2<\epsilon+P_1+P_2$" is not correct. Take $P_1=10,P_2=1,\epsilon=10$. You have $20<10+10+1$ and $2<10+10+1$. – Chiba Feb 16 '16 at 22:55
• Why? 20 < 10+ 10+1! I said "OR" and not "AND". – Shreesh Feb 17 '16 at 5:11