algorithm - NP-Complete reduction -

the problem states want show independent set poly-time reduces relative prime sets, more formally independent set <p relative prime sets.

i need provide reduction f ind.set rel. prime sets, where

- input of f must graph g , integer k, k denotes size of independent set.

- output of f must set s of integers , integer t, t denotes number of pairwise relative prime numbers in set s.

definition of relative prime sets (decision version):

it takes set p of n-integers , integer t 1 n.

returns yes if there's subset of p, t-many pairwise relative primes. is, a, b in a, must true gcd(a, b) = 1.

returns no otherwise

so far have come-up believe reduction, not sure if valid , want double check knows how this.

reduction:

let g graph.let k indicate size of independent set. want find-out if there exists independent set of size k in g. since problem np-complete, if can solve np-complete problem in poly-time, know can solve independent set in poly-time. chose reduce independent set relative prime sets.

we take graph g , label vertices 1 n pr definition of input relative prime sets. find gcd of each node every other node in g. draw edge between nodes have gcd(a, b) = 1. when graph complete, @ nodes , determine nodes not connected each other via edge. create sets nodes. return set containing nodes along integer t denoting number of integers in set. set of relative prime numbers in graph g , greatest independent set of g.

suppose 2 graphs, each of 4 nodes. on graph one, nodes connected in line max-independent set 2. graph 2 complete graph each node connected each other node, max-independent set 1.

it sounds reduction result in same set each graph, leading incorrect result independent set.