Reduce 3-SAT to independent set problems

[GiggleLiu]

No description provided.

[SciCodePhy]

Reduce 3-SAT to Independent Set Problem

I. Definitions and Background

I-A. SAT

• 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.

III. References

Core References:

1. The Nature of Computation
2. https://www.cs.umd.edu/class/fall2017/cmsc451-0101/Lects/lect20-np-3sat.pdf

Other References:

3. https://courses.engr.illinois.edu/cs374/fa2020/lec_prerec/23/23_2_0_0.pdf

[SciCodePhy]

Finished in #65