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!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.)

Improve this answer
$\endgroup$
7
  • $\begingroup$ Is A the whole graph? $\endgroup$
    – guest
    Jul 28, 2015 at 21:58
  • $\begingroup$ No, $A$ is any set of vertices. $\endgroup$
    – Yuval Filmus
    Jul 28, 2015 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, 2015 at 22:05
  • $\begingroup$ I mean that the GCD tells you which edges are covered by the vertices. $\endgroup$
    – Yuval Filmus
    Jul 28, 2015 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, 2015 at 22:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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