Nov8Reductions

Complement Of Independent Sets
c
d
a
b
e
c
d
a
b
e

Clique
c
d
a
b
e

3-SAT
(a ∨¬b∨ c)∧ (¬a ∨ b ∨ ¬c)
LP:a + (1 - b) + c ≥ 1(1 - a) + b + (1 -c) ≥10≤a, b, c≤1

3-SAT CLIQUE
(a ∨¬b∨ c)∧ (¬a ∨ b ∨ ¬c)
a
¬b
c
¬a
b
¬c
Comment cards
https://goo.gl/RKd8vq

3-SAT CLIQUE: more interesting case
(a ∨b∨¬c)∧ (¬a ∨ c ∨ d)∧ (¬ a ∨¬b∨¬c)∧(a ∨c∨¬d)
a
c
d
b
¬c
¬a
¬a
¬b
¬c
a
c
¬d

3-SAT CLIQUE: satisfying assignment
(a ∨b∨¬c)∧ (¬a ∨ c ∨ d)∧ (¬ a ∨¬b∨¬c)∧(a ∨c∨¬d)
a
c
d
b
¬c
¬a
¬a
¬b
¬c
a
c
¬d

Complement Graphs
c
d
a
b
e
c
d
a
b
e