2
$\begingroup$

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:

enter image description here

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.

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

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 < \epsilon < 1/\hspace{.02 in}2$ ​ ​ ​ .

|cite|improve this answer
$\endgroup$
  • $\begingroup$ In adjacency matrix, $g_{ii}=0$ for all $i$, no? How can I satisfy the inequality then? $\endgroup$ – Chiba Feb 13 '16 at 10:38
  • $\begingroup$ I've now fixed that. ​ ​ $\endgroup$ – user12859 Feb 13 '16 at 17:18
  • $\begingroup$ 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 $\endgroup$ – Chiba Feb 15 '16 at 23:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.