# All Science Fair Projects

## Science Fair Project Encyclopedia for Schools!

 Search    Browse    Forum  Coach    Links    Editor    Help    Tell-a-Friend    Encyclopedia    Dictionary

# Science Fair Project Encyclopedia

For information on any area of science that interests you,
enter a keyword (eg. scientific method, molecule, cloud, carbohydrate etc.).
Or else, you can start by choosing any of the categories below.

# Independent set problem

In mathematics, the independent set problem (IS) is a question in combinatorics, known to be an NP-complete problem.

## Description

Given a graph G, an independent set is a subset of its vertices that are pairwise not connected together.

Input:

• A graph G
• An integer K.

Question:

• Does G have an independent set of at least size K?

## Proof that Independent Set is NP-complete

This is by reduction from 3-SAT, a version of the Boolean satisfiability problem.

1. Certificate: Check that no vertices are connected.

This can easily be verified in polynomial time.

2. 3-CNF-SAT->IS transformation

• 3-CNF-SAT (Given):
• Variables x1, x2, ..., xn
• Clauses c1, c2, ..., cm
• IS (Construction of Graph):
• 1 vertex for each occurrence of each literal (3m vertices)
• Connect two vertices when:
• They are conflicting (i.e. x1, ~x1)
• They are in the same clause

This transformation can be performed in polynomial time.

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

• Yes->Yes:
• Pick only one literal from 3-CNF-SAT solution
• Per definition of satisfiability, vertices in our graph represented by this literal will not be connected to another vertex in the ""same clause"" or to a conflicting vertex
• Hence, the node is part of the Independent Set
• No->No:
• Use contrapositive (Yes<-Yes aka 3-CNF-SAT<-IS).
• Select an independent set of size m.
• By construction, vertices are linked to conflicting literals and literals in the same clause.
• Therefore, these can not be part of an independent set.
• Hence, only vertices in an independent set will satisfy 3-CNF-SAT.
03-10-2013 05:06:04