|
|
|
|
|
Independent Set ProblemIn 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: 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.
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|