The proof that the Clique problem is NP-complete depends on a construction given in Theorem 34.11 (p. 1087), which reduces 3SAT
to Clique. Apply this construction to the 3SAT instance: (u+v+w)(-v+-w+x)(-u+-x+y)(x+-y+z)(u+-w+-z) Note that - denotes negation, e.g., -v stands for the literal NOT v. Also, remember that the construction involves the creation of vertices which here we denote [i,j]. The vertex [r,i] corresponds to the ith literal of the rth clause. For example, [1,2] corresponds to the occurrence of literal v in the 3SAT instance above. After performing the construction, identify from the list below the one pair of vertices that does have an edge between them. a) [2,2] and [4,3] b) [1,3] and [5,2] c) [4,3] and [5,3] d) [1,2] and [2,1]
1 answer:
You might be interested in