\documentclass{article}
\usepackage[utf8]{inputenc}
\title{CS301HW13}
\author{ }
\date{May 2021}
\begin{document}
\maketitle
\section*{Part One}
\section*{Answer the following questions regarding HITTING\textunderscore SET and VERTEX\textunderscore COVER as defined below.}
HITTING\textunderscore SET \(= { | S \) is a set, T is a set of subsets of S, and h is an integer where there is S’ \( ⊆ S with |S’| = h and S’ contains at least one element from each set in T} \)
VERTEX\textunderscore COVER = {
a. Find a hitting set S’ of size h=2 for the sets S = {a, b, c, d, e, f, g} and T = {{a,b,c}, {c,d,e}, {e,f,g}}.
b. Find a vertex cover of size 2 for the graph G = (V, E) where V = {a, b, c, d, e} and E = {{a,b}, {b,c}, {a,d}, {b,e}, {d,e}}.
c. Describe the certificate for a polynomial time verifier for VERTEX\textunderscore COVER.
d. Describe the certificate for a polynomial time verifier for HITTING\textunderscore SET.
e. Describe a polynomial time reduction from VERTEX\textunderscore COVER to HITTING\textunderscore SET.
\section*{2 Use the reductions described in the book to perform the following conversions.}
\section*{2a}
\Phi = ( a \vee b ) \wedge (a \vee \bar{b} \vee c \vee d)
\section*{2b}
\Phi = (a \vee b \vee b) \wedge (\bar{a} \vee \bar{b} \vee \bar{b})
\section*{2c}
\Phi = (a \vee b \vee b) \wedge (\bar{a} \vee \bar{b} \vee \bar{b})
\end{document}