Main Page | See live article | Alphabetical index

Independent Set problem

The Independent Set (IS) problem is an NP-complete problem.

Description

An independent set is defined as a subset of a vertices in a graph that are not connected together.

Input:

Question:

Proof of Independent Set being NP-complete

(Reduce from 3-CNF-SAT a version of the Boolean satisfiability problem)

1. Certificate: Check that no vertices are connecting.

Can easily be verified in polynomial time.

2. 3-CNF-SAT->IS transformation

This transformation can be performed in polynomial time.

3. Proof of correctness (note: is not formal or complete)