3-Coloring is NP-Hard
1 like926 views
The document presents a proof that 3-coloring is NP-hard. It first defines 3-SAT and 3-coloring problems. It then describes a reduction that maps a 3-SAT formula 陸 to a graph G陸 such that 陸 is satisfiable if and only if G陸 has a 3-coloring. The reduction uses literal and clause gadgets to encode the formula as a graph. It is proved that a satisfying assignment for 陸 can be used to 3-color G陸, and vice versa, showing that solving 3-coloring is at least as hard as solving 3-SAT.
3-Coloring is NP-Hard
- 1. 3-Coloring is NP-Hard Feliciano colella December 4, 2014
- 2. Algorithm Design Homework 02 Outline of the presentation 1. Denition of 3-Satisability. 2. Denition of 3-Coloring. 3. Proof that 3-Sat P 3-Color. Feliciano colella 3-Coloring is NP-Hard December 4, 2014 2 / 8
- 3. Algorithm Design Homework 02 The problems 3-Satisability Input CNF formula 陸 where each clause contains exactly 3 dierent literals. Output Satisfying truth assignment for the formula 陸. Feliciano colella 3-Coloring is NP-Hard December 4, 2014 3 / 8
- 4. Algorithm Design Homework 02 The problems 3-Satisability Input CNF formula 陸 where each clause contains exactly 3 dierent literals. Output Satisfying truth assignment for the formula 陸. k-Coloring Input A graph G = (V , E) with |V | = n vertices and |E| = m edges. Output A k-Coloring c : V {1, . . . , k}, s.t. (x, y) E, C(x) = C(y). Feliciano colella 3-Coloring is NP-Hard December 4, 2014 3 / 8
- 5. Algorithm Design Homework 02 The reduction 3-Coloring is in NP Certicate A 3-Coloring c : V {1, 2, 3} Certier Check if (u, v) E, c(u) = c(v) Hardness Show that the formula 陸 is satisable IFF exist a 3-Coloring for the graph G. Feliciano colella 3-Coloring is NP-Hard December 4, 2014 4 / 8
- 6. Algorithm Design Homework 02 The gadgets Literals Gadget Clause gadget Feliciano colella 3-Coloring is NP-Hard December 4, 2014 5 / 8
- 7. Algorithm Design Homework 02 The gadgets Literals Gadget Clause gadget x1 測x1 x2 測x2 xn 測xn R T F Feliciano colella 3-Coloring is NP-Hard December 4, 2014 5 / 8
- 8. Algorithm Design Homework 02 The gadgets Literals Gadget Clause gadget x1 測x1 x2 測x2 xn 測xn R T F ci1 ci2 ci3 R T F Feliciano colella 3-Coloring is NP-Hard December 4, 2014 5 / 8
- 9. Algorithm Design Homework 02 The construction x1 測x1 x2 測x2 xn 測xn R T F c13 c12 c11 c23 c22 c21 c 3 c 2 c 1 Feliciano colella 3-Coloring is NP-Hard December 4, 2014 6 / 8
- 10. Algorithm Design Homework 02 The theorem Theorem A CNF Formula 陸 is satisable exists a 3-Coloring for the graph G陸. Feliciano colella 3-Coloring is NP-Hard December 4, 2014 7 / 8
- 11. Algorithm Design Homework 02 The theorem Theorem A CNF Formula 陸 is satisable exists a 3-Coloring for the graph G陸. 陸 is satisable = G陸 is 3-Colorable Take a truth assignment for 陸 and color the literals gadgets; Each clause have at least 1 literal set to True; All the clause gadget can be colored with respect to the constraint; We have a 3-Coloring. Feliciano colella 3-Coloring is NP-Hard December 4, 2014 7 / 8
- 12. Algorithm Design Homework 02 The theorem Theorem A CNF Formula 陸 is satisable exists a 3-Coloring for the graph G陸. G陸 is 3-Colorable = 陸 is satisable Take a 3-Coloring for G陸; If a literal is colored with True, set it to True in the formula 陸; For any clause, it cannot be that all the literals are True or False. Otherwise we would have a clause gadget colored to False, but this is impossible since they are connected to Base and False and we have started from a 3-Coloring for G陸; We have hence correct a truth assignment for 陸 Feliciano colella 3-Coloring is NP-Hard December 4, 2014 7 / 8
- 13. Thank you for the attention.