|
|
Definition
Given undirected graph, G = (V,E). There exists a subset A ⊆ V , such that A is an independence set, if and only if, no two vertices in A are joined by an edge.
Polynomial Certifier
Question: Given undirected graph, G = (V,E) and a number k. Does there exist an independence set of size at most k?
Reduction from 3-SAT by encoding with Gadget
The constructions is as follow: G contains 3 vertices for each clause, one for each literal. Connect 3 literals in a clause in a triangle. Connect literal to each of its negations.
Claim 4.12.1.1. 3-SAT ≡p Independent Set.
G contains independent set of size k = |Φ| if and only if Φ is satisfiable.
G contains independent set of size k = |Φ|⇒ Φ is satisfiable.
Proof. Let IS be a size k Independent Set in G. Then, IS must contain exactly one vertex from each triangle. We simply set all the literals in IS to true. This implies that at least one literal in each clause gets a true value. Thus, Φ is satisfiable. __
Φ is satisfiable ⇒ G contains independent set of size k = |Φ|
Proof. If Φ is satisfiable, each clause must have at least one true literal. If we select a true literal from each clause, then the corresponding vertices must form an Independent Set of size k. __
