# NP Complete Subset GCD Proof

$SubsetGCD$ is described by the following:

instance: A set of positive integers $S$ and an integer $k$
question: does there exist a subset $S'$ of $S$ of size $k$ such that $GCD(S') = GCD(S)$

Prove that $SubsetGCD$ is np complete.

The hint for the problem is to reduce $VertexCover$ to $SubsetGCD$

I know what I'm supposed to do. Given an instance of $VertexCover$ convert it into the form of $SubsetGCD$ such that there exists a vertex cover of size $k$ if and only if there exists a subset $S'$ of size $k$ such that $GCD(S') = GCD(S)$

Since the vertex cover and subset are of size $k$ I feel like the vertices should correspond to the members of $S$ so that the vertex cover itself is the subset $S'$

Therefore, the important part is how to define the edges connecting the verticies. I've tried edges if the GCD of the endpoints is GCD(S), if the GCD of the endpoints is not GCD(S), edges connected to a vertex must be have GCD(S) and can't have a GCD greater than GCD(S) for all immediate neighbours etc.

I've also tried reducing Clique to the Subset GCD problem with no luck. Any help would really be appreciated!

Hint: Associate each edge $e$ with a prime $p_e$, and each vertex $v$ with a number $n_v \in S$. Choose $n_v$ so that the GCD of $\{n_v : v \in A\}$ encodes the set of edges covered by the vertices in $A$.
• No, $A$ is any set of vertices. – Yuval Filmus Jul 28 '15 at 21:59