You have to show (no explanations necessary) how the following reductions work. Please remember that if we are looking at a reduction from A to B, the A instance might be a YES instance or might be a NO instance. (a) In class we saw the reduction from the Hamiltonian cycle problem to the 0-1 TSP problem. Show what will be the TSP instance (by showing the graph G′and the number K′) if we start with the Hamiltonian cycle instance G in Fig HW4Q2a. (b) In class we studied the reduction from CLIQUE to I.S. Show what will be the I.S. instance (by showing the graph G′and the number K′) if we start with the CLIQUE instance with K = 3 and the graph in Fig HW4Q2b. (c) In class we studied the reduction from SAT to CLIQUE. Show what will be the CLIQUE instance (by showing the graph G and the number K) if we start with the following SAT instance: (complement is shown with the − sign, so −x stands for the complement of x. (x ∨(−w) ∨(−z)) ∧((−x) ∨w ∨(z)) ∧((−x) ∨(−w))
You have to show (no explanations necessary) how the following reductions work. Please remember that if
we are looking at a reduction from A to B, the A instance might be a YES instance or might be a NO instance.
(a) In class we saw the reduction from the Hamiltonian cycle problem to the 0-1 TSP problem. Show what will be
the TSP instance (by showing the graph G′and the number K′) if we start with the Hamiltonian cycle instance
G in Fig HW4Q2a.
(b) In class we studied the reduction from CLIQUE to I.S. Show what will be the I.S. instance (by showing the graph
G′and the number K′) if we start with the CLIQUE instance with K = 3 and the graph in Fig HW4Q2b.
(c) In class we studied the reduction from SAT to CLIQUE. Show what will be the CLIQUE instance (by showing
the graph G and the number K) if we start with the following SAT instance: (complement is shown with the −
sign, so −x stands for the complement of x.
(x ∨(−w) ∨(−z)) ∧((−x) ∨w ∨(z)) ∧((−x) ∨(−w))
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 1 images
