Boolean Algebra [see 'Reduce k-SAT to 3-SAR' issue]
Cook-Levin Theorem: 3-SAT is NP-complete.
I-B. Independent Set Problem (IS)
Independent Set: For an undirected graph $G$ and its subset $S \subset G $, $S$ is independent if all the vertices in $S$ cannot be connected by edges (aka: not adjacent).
Independent Set Problem: Given a graph $G$ and an integer $k$, check whether $G$ has an independent set of size $k$.
II. Proof (3-SAT <= IS)
We can translate an arbitrary 3-SAT CNF (an instance of 3-SAT) to an graph $G$ associated with $k$ (an instance of IS) [Ref. 2].
Step-0: The number of clauses in this CNF corresponds to $k$.
Step-1: The new graph $G$ will have 3 $k$ vertices (all the literals in all the clauses; There can be repeated literals).
Step-2: For each clause such as $x_1 \lor x_2 \lor x_3$, we connect edges between all these three vertices.
Step-3: We connect all the literals to their negations.
It can proven that:
This CNF is satisfiable if and only if the generated $G$ has an independent set of size $k$.
The generation of the new graph is within polynomial time.
Reduce 3-SAT to Independent Set Problem
I. Definitions and Background
I-A. SAT
I-B. Independent Set Problem (IS)
II. Proof (3-SAT <= IS)
We can translate an arbitrary 3-SAT CNF (an instance of 3-SAT) to an graph $G$ associated with $k$ (an instance of IS) [Ref. 2].
It can proven that:
III. References
Core References:
Other References: