CMSC 451 SAT Coloring Hamiltonian Cycle TSP Slides By Carl Kingsford Department of Computer Science University of Maryland College Park Based on Sects 8 2 8 7 8 5 of Algorithm Design by Kleinberg Tardos Boolean Formulas Boolean Formulas Variables x1 x2 x3 can be either true or false Terms t1 t2 t tj is either xi or x i meaning either xi or not xi Clauses t1 t2 t stands for OR A clause is true if any term in it is true Example 1 x1 x 2 x 1 x 3 x2 v 3 Example 2 x1 x2 x 3 x 2 x1 Boolean Formulas Def A truth assignment is a choice of true or false for each variable ie a function v X true false Def A CNF formula is a conjunction of clauses C1 C2 Ck Example x1 x 2 x 1 x 3 x2 v 3 Def A truth assignment is a satisfying assignment for such a formula if it makes every clause true SAT and 3 SAT Satisfiability SAT Given a set of clauses C1 Ck over variables X x1 xn is there a satisfying assignment Satisfiability 3 SAT Given a set of clauses C1 Ck each of length 3 over variables X x1 xn is there a satisfying assignment Cook Levin Theorem Theorem Cook Levin 3 SAT is NP complete Proven in early 1970s by Cook Slightly different proof by Levin independently Idea of the proof encode the workings of a Nondeterministic Turing machine for an instance I of problem X NP as a SAT formula so that the formula is satisfiable if and only if the nondeterministic Turing machine would accept instance I We won t have time to prove this but it gives us our first hard problem Reducing 3 SAT to Independent Set Thm 3 SAT P Independent Set Proof Suppose we have an algorithm to solve Independent Set how can we use it to solve 3 SAT To solve 3 SAT you have to choose a term from each clause to set to true but you can t set both xi and x i to true How do we do the reduction 3 SAT P Independent Set x1 x2 x3 x2 x3 x4 x1 x2 x4 x1 x2 x2 x3 x3 x1 x4 x2 x4 Proof Theorem This graph has an independent set of size k iff the formula is satisfiable Proof If the formula is satisfiable there is at least one true literal in each clause Let S be a set of one such true literal from each clause S k and no two nodes in S are connected by an edge If the graph has an independent set S of size k we know that it has one node from each clause triangle Set those terms to true This is possible because no 2 are negations of each other Graph Coloring Graph Coloring Graph Coloring Problem Graph Coloring Problem Given a graph G can you color the nodes with k colors such that the endpoints of every edge are colored differently Notation A k coloring is a function f V 1 k such that for every edge u v we have f u 6 f v If such a function exists for a given graph G then G is k colorable Special case of k 2 How can we test if a graph has a 2 coloring Special case of k 2 How can we test if a graph has a 2 coloring Check if the graph is bipartite Unfortunately for k 3 the problem is NP complete Theorem 3 Coloring is NP complete Graph Coloring is NP complete 3 Coloring NP A valid coloring gives a certificate We will show that 3 SAT P 3 Coloring Let x1 xn C1 Ck be an instance of 3 SAT We show how to use 3 Coloring to solve it Reduction from 3 SAT We construct a graph G that will be 3 colorable iff the 3 SAT instance is satisfiable For every variable xi create 2 nodes in G one for xi and one for x i Connect these nodes by an edge xi xi Create 3 special nodes T F and B joined in a triangle B T F Connecting them up Connect every variable node to B x2 x1 x2 x1 x3 B T F x3 Properties Properties Each of xi and x i must get different colors Each must be different than the color of B B T and F must get different colors Hence any 3 coloring of this graph defines a valid truth assignment Still have to constrain the truth assignments to satisfy the given clauses however Connect Clause t1 t2 t3 up like this T t1 F t2 t3 Suppose Every Term Was False What if every term in the clause was assigned the false color Connect Clause t1 t2 t3 up like this B T t1 F t2 t3 Connect Clause t1 t2 t3 up like this B T t1 F t2 t3 Connect Clause t1 t2 t3 up like this B T t1 F t2 t3 Connect Clause t1 t2 t3 up like this B T t1 F t2 t3 Suppose there is a 3 coloring Top node is colorable iff one of its terms gets the true color Suppose there is a 3 coloring We get a satisfying assignment by Setting xi true iff vi is colored the same as T Let C be any clause in the formula At least 1 of its terms must be true because if they were all false we couldn t complete the coloring as shown above Suppose there is a satisfying assignment Suppose there is a satisfying assignment We get a 3 coloring of G by Coloring T F B arbitrarily with 3 different colors If xi true color vi with the same color as T and v i with the color of F If xi false do the opposite Extend this coloring into the clause gadgets Hence the graph is 3 colorable iff the formula it is derived from is satisfiable General Proof Strategy General Strategy for Proving Something is NP complete 1 Must show that X NP Do this by showing there is an certificate that can be efficiently checked 2 Look at some problems that are known to be NP complete there are thousands and choose one Y that seems similar to your problem in some way 3 Show that Y P X Strategy for Showing Y P X One strategy for showing that Y P X often works 1 Let IY be any instance of problem Y 2 Show how to construct an instance IX of problem X in polynomial time such that If IY Y then IX X If IX X then IY Y Hamiltonian Cycle Hamiltonian Cycle Hamiltonian Cycle Problem Hamiltonian Cycle Given a directed graph G is there a cycle that visits every vertex exactly once Such a cycle is called a Hamiltonian cycle Hamiltonian Cycle is NP complete Theorem Hamiltonian Cycle is NP complete Proof First HamCycle NP Why Second we show 3 SAT P Hamiltonian Cycle Suppose we have a black box to …