# 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.

• I think you will need $\tau$ also in the definition of the problem. – Shreesh Feb 13 '16 at 7:38
• I just divide by $\tau$ both sides of the inequality to use less variables. Is it wrong to do that? – Chiba Feb 13 '16 at 10:34
• The problem won't be similar then. $\tau$ does not divides the denominator. – Shreesh Feb 13 '16 at 10:44
• Yes, my bad. I will edit the question. Thanks. – Chiba Feb 13 '16 at 10:50

$\mathbf{G}$ ​ = ​ adjacency matrix + identity matrix ​ ​ ​ and ​ ​ ​ $\tau = 2$ ​ ​ ​ and ​ ​ ​ $0 < \epsilon < 1/\hspace{.02 in}2$ ​ ​ ​ .
• In adjacency matrix, $g_{ii}=0$ for all $i$, no? How can I satisfy the inequality then? – Chiba Feb 13 '16 at 10:38
• Very helpful. Thank you. If I restrict the $g_{ij}$ to be positive, can we still use independent set? I was thinking to set $g_{ij}=1/a$ if $\{i,j\}$ is not an edge in the graph, where $a$ is very big number. Another alternative, maybe, to reduce the version with non-negative $g_{ij}$ to the version with positive $g_{ij}$. What do you think @Ricky Demer – Chiba Feb 15 '16 at 23:59