CIS 675: Algorthms – Spring 2019 Homework 10

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.

• Chapters 8 and 9 of DPV

Problems

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).