NP-full reduction

The problem is that we want to show that independent poly-times are reduced to Relative Prime Sets, more formally Independent Set <p Relative Prime Sets

.

I need to provide the abbreviation f from ind.set to rel. simple sets, where

- input f must be a graph G and an integer k, where k denotes the size of the independent set.

- output f must be a set S of integers and an integer t, where t denotes the number of pairwise relative primes in the set S.

Determination of relative primes (solution version):

a set of P n-integers and an integer t from 1 to n are taken.

returns yes if there is a subset A of P, with t-many pairwise relative primes. That is, for all a, b in A, it must be true that gcd (a, b) = 1.

does not return otherwise

So far, I've come up with what I think is a shortcut, but I'm not sure if it's actually valid and I want to double check it with someone who knows how to do it.

Decrease:

Let G be a graph. Let k denote the size of an independent set. Then we want to find out if there is an independent set of dimension k in G. Since this problem is NP-Complete, if we can solve another NP-Complete problem in multi-user time, we know that we can also solve Independent Set in poly-time. Therefore, we decided to reduce the independent set on the Relative Prime Sets.

Take a graph G and place its vertices from 1 to n, since pr is the definition of an input for relative simple sets. Then we will find the gcd of each node to all other nodes in G. Draw an edge between the nodes with gcd (a, b) = 1. When the graph is complete, we will look at the nodes and determine which nodes are not connected to each other over the edge. We create sets for these nodes. Let's return a set containing most of the nodes along with an integer t, which denotes the number of integers in the set. This is the set of the most relative primes of numbers in the graph G, as well as the largest independent set G.