CODEWITHSUNDEEP
graphnp
Jun Hao
Jun Hao

Reputation: 209

Reducing independent set to clique?

Show that given a graph G and a number k, there is some way to transform it to a graph H such that G has an independent set of size of size at least k if and only if H has a clique of size at least k.

Upvotes: 2

Views: 7968

Answers (1)

templatetypedef
templatetypedef

Reputation: 373482

An independent set is a group of nodes where for any pair of nodes in the set, there is not an edge between those nodes. A clique is a group of nodes where for any pair of nodes in the set, there is an edge between those nodes. Therefore, an independent set in a graph G is a clique in the complement of G and vice-versa.

Given this, a simple transformation would be given G and k to produce Gc (the complement of G) and k. Then, G has an independent set of size k if and only if Gc has a clique of size k.

Hope this helps!

Upvotes: 6

Related Questions