CIS 675: Algorthms – Spring 2019
Homework 10

Version 1   (29 March 2019)




  1. (19 points) DPV, Exercise 8.1.

    Hint: Binary search.

  2. (20 points) DPV, Exercise 8.2.

    Hint: Ask the decision problem about certain variations of the input graph.

  3. (20 points) DPV, Exercise 8.3.

    Hint: This is really easy.

  4. (20 points) DPV, Exercise 8.9

    Specifically: Let (C_1,\dots,C_k) be an instance of SAT where C_1,\dots,C_k be the clauses to be satisfied. Let v_1,\dots,v_m be the variables in this instance. We construct an instance of Hitting Set as follows:
    For i=1,\dots,k, define S_i= the set of literals in C_i.
    For i=1,\dots,m, define S_{k+i} = \{\, v_i,\overline{v_i}\,\}.
    Let b=m.

    Show that (C_1,\dots,C_k) is a yes-instance of SAT if and only if ((S_1,\dots,S_{k+m}),m) is a yes-instance of Hitting Set.

  5. (21 points) DPV, Exercise 8.10 parts (a), (c), and (d).