CIS 675: Algorthms – Spring 2019
Homework 10

Version 1 (29 March 2019)

Abbreviations

DPV = Algorithms, by S. Dasgupta, C. Papadimitriou, and U. Vazirani, McGraw-Hill, 2007.
PG = Problems on Algorithms, 2/e, by Ian Parberry and William Gasarch.

(19 points) DPV, Exercise 8.1.

Hint: Binary search.
(20 points) DPV, Exercise 8.2.

Hint: Ask the decision problem about certain variations of the input graph.
(20 points) DPV, Exercise 8.3.

Hint: This is really easy.
(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.
(21 points) DPV, Exercise 8.10 parts (a), (c), and (d).