|
|
Definition
Given an undirected graph G does there exists a way to color the nodes red, green, and blue so that no adjacent nodes have the same color?
Polynomial Certifier
Given an undirected graph G does there exists a way to color the nodes red, green, and blue so that no adjacent nodes have the same color?
Reduction from 3-SAT by encoding with gadget
For each literal, create a node. Create 3 new nodes T, F, B; connect them in a triangle, and connect each literal to B. Connect each literal to its negation. For each clause, add gadget of 6 nodes and 13 edges.
The variable gadget for a variable a is also a triangle joining two new nodes labelled a and a to node X in the truth gadget. Node a must be colored either True or False, and so node a must be colored either False or True, respectively. Finally, each clause gadget joins three literal nodes to node T in the truth gadget using five new unlabelled nodes and ten edges; see the figure below. If all three literal nodes in the clause gadget are colored False, then the rightmost vertex in the gadget cannot have one of the three colors. Since the variable gadgets force each literal node to be colored either True or False, in any valid 3-coloring, at least one of the three literal nodes is colored True. I need to emphasize here that the final graph contains only one node T, only one node F, only one node a for each variable a, and so on.
Claim 4.16.3.1. 3-SAT ≤p 3-Color
Given 3-SAT instance Φ is satisfiable if and only if the graph is 3-colorable.
Given 3-SAT instance Φ is satisfiable ⇒ the graph is 3-colorable.
Proof. Suppose 3-SAT formula Φ is satisfiable. Color all true literals T. Color node below green node F, and node below that B. Color remaining middle row nodes B. Color remaining bottom nodes T or F as forced. __
The graph is 3-colorable ⇒ 3-SAT instance Φ is satisfiable.
Proof. Suppose graph is 3-colorable. Consider assignment that sets all T literals to true. (ii) ensures each literal is T or F. (iii) ensures a literal and its negation are opposites (iv) ensures at least one literal in each clause is T. __
