# NP-Hardness of $\{ (S,k) | \exists S' \subset S \text{ s.t } \forall x \neq y \in S' \gcd(x,y)=1 \text{ and } \sum_{s \in S'} s \geq k \}$

I have been practicing NP-Hardness reductions and have been particularly interested in the language $$L = \{ (S,k) | \exists S' \subset S \text{ s.t } \forall x \neq y \in S' \gcd(x,y)=1 \text{ and } \sum_{s \in S'} s \geq k \}$$. I am trying to prove that $$L$$ is NP-Hard and have come up with the following reduction from independent set:

$$f(G,k)$$:

• First, label the vertices 1 to $$|V|$$ arbitrarily.
• For each edge $$(i,j) \in E$$ let $$p_{ij}$$ be the $$|V|+1$$ digit base $$|E|+1$$ number beginning with a 1 and the remaining digits zero except for the $$i$$th and $$j$$th digits who are 1. (e.g $$p_{12} = 1110000_{|E|+1}$$ for a graph with 6 vertices on $$|E|$$ edges).
• Then, for each vertex $$v$$ define $$s_v := \displaystyle (|E|+1)^{(D - \deg(v) + 1)|V|} \prod_{i=v \text{ or } j = v} p_{ij}$$ where $$D$$ is the maximum degree of any vertex in $$G$$.
• Finally, output $$\bigg( \big(\{ p_{ij} : (i,j) \in E \} \cup \{s_v : v \in V \} \big), \; k(|E|+1)^{(D+1)|V|} \bigg)$$

It is clear to me that if $$(G,k)$$ is in independent set, then the output of the above will be in $$L$$. However, I am still not quite convinced that if $$f(G,k) \in L$$ then $$(G,k)$$ is in independent set. My reasoning is that if there is no independent set of size (at least) $$k$$, then we cannot take $$k$$ separate $$s_v$$ numbers to include in our sum, so the target value cannot be reached - and by using base $$|E|+1$$ we guarantee there is no funky carrying going on that may interfere with this.

Therefore my main question is am I overlooking some edge cases arising from strange graphs in my reduction or have I been worrying over nothing.

Additionally, I am curious as to whether there is any further study of this language, possibly relating to the taxman game discussed here https://faculty.etsu.edu/beelerr/taxman-talk.pdf.