1
$\begingroup$

$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!

$\endgroup$
1
$\begingroup$

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

If you get stuck, try first showing that SubsetLCM is NP-complete. (LCM is Least Common Multiple.)

$\endgroup$
  • $\begingroup$ Is A the whole graph? $\endgroup$ – guest Jul 28 '15 at 21:58
  • $\begingroup$ No, $A$ is any set of vertices. $\endgroup$ – Yuval Filmus Jul 28 '15 at 21:59
  • $\begingroup$ I'm a little confused by how you are describing this. Choose numbers from S for the vertices. What do you mean by the GCD encodes the edges covered by the vertices? $\endgroup$ – guest Jul 28 '15 at 22:05
  • $\begingroup$ I mean that the GCD tells you which edges are covered by the vertices. $\endgroup$ – Yuval Filmus Jul 28 '15 at 22:06
  • $\begingroup$ You say each edge is associated with a prime, but how do you know how many edges to make and which vertices are at the end points. $\endgroup$ – guest Jul 28 '15 at 22:12

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.