16.16. Reduction of Clique to Independent Set¶
16.16.1. Clique to Independent Set¶
The following slideshow shows that an instance of CLIQUE can be reduced to an equivalent instance of INDEPENDENT SET in polynomial time.
This reduction can help in providing an NP Completeness proof for the Independent Set problem.
The following exercise gives you a chance to reproduce the proof that INDEPENDENT SET is NP-Complete. This will help to confirm whether you understand the process.
