1
$\begingroup$

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.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.