Select the maximum number of links to satisfy per-link constraint. How to prove is NP-hard? I asked, incorrectly, my previous question here. I would like to thank D.W. for his answer though. He answeres that the problem is polynomial time solvable. The thing is that the cited paper shows that it is NP-hard. So I corrected my question. But I don't understand, am I missing something? In the paper, as shows the figure (page 2, right column in the paper), the authors says:



They show that that problem is NP-hard.

So here is the new question. 

Instance: A matrix of size $n\times n$ of non-negative real numbers $\mathbf{G}=\left[g_{ij}\right]$, a positive number $k\le n$, and a positive number $\tau$ and a positive number $\epsilon$.

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

$$\dfrac{g_{ii}}{\epsilon-g_{ii}+\sum\limits_{j\in S}g_{ij}}\geq \tau,\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 $g_{ij}$ 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 paper, but the reduction is very hard for me.
Even when each entry of G is in {0,1}, that is W[1]-hard by reduction from independent set:

$\mathbf{G}$ ​ = ​ adjacency matrix + identity matrix ​ ​ ​ and ​ ​ ​ $\tau = 2$ ​ ​ ​ and ​ ​ ​ $0 &lt; \epsilon &lt; 1/\hspace{.02 in}2$ ​ ​ ​ .