%
% Assignment 7e for CS3530 Computational Theory:
% Complexity
% Fall 2023
%
% Problems taken from Sipser
%

\documentclass{article}

\usepackage[margin=1in]{geometry}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
\usepackage{ae,aecompl}
\usepackage{emp,ifpdf}
\usepackage{graphicx}
\usepackage{enumerate}

\ifpdf\DeclareGraphicsRule{*}{mps}{*}{}\fi

\empaddtoTeX{\usepackage{amsmath}}
\empprelude{input boxes; input theory}

% skip for paragraphs, don't indent
\parskip 6pt plus 1pt
\parindent=0pt
\raggedbottom

% a list environment with no bullets or numbers
\newenvironment{indentlist}{\begin{list}{}{\addtolength{\itemsep}{0.5\baselineskip}}}{\end{list}}

\begin{document}
\begin{empfile}

\begin{center}
\textbf{\Large CS 3530: Assignment 7e} \\[2mm]
Fall 2023
\end{center}

\raggedright


\section*{Problem 7.35 (20 points)}

\subsection*{Problem}

A subset of the nodes of a graph $G$ is a \textbf{\textit{dominating set}} if every other node of $G$
is adjacent to some node in the subset.  Let

$$\textsc{Dominating-Set} = \{ \langle G, k \rangle | G \text{ has a dominating set with } k \text{ nodes } \}$$.

Show that \textsc{Dominating-Set} is NP-complete.  You may assume that \textsc{Vertex-Cover} is NP-complete.

\emph{Note:} In order to receive credit for this assignment, you must complete the full NP-completeness proof process outlined here.

\subsection*{Prove \textsc{Dominating-Set} $\in$ NP}

\subsubsection*{Describe a certificate for \textsc{Dominating-Set}}
\subsubsection*{Provide a polynomial verifier for \textsc{Dominating-Set}}

\subsection*{Prove \textsc{Dominating-Set} is NP-hard}

Given that \textsc{Vertex-Cover} is NP-complete,
show that $\textsc{Vertex-Cover} \le_P \textsc{Dominating-Set}$ with the following steps.

\subsubsection*{Provide reduction from \textsc{Vertex-Cover} to \textsc{Dominating-Set}}

\subsubsection*{Prove reduction from \textsc{Vertex-Cover} to \textsc{Dominating-Set} is polynomial}

\subsubsection*{Show \textsc{Vertex-Cover} has a size $k$ cover if \textsc{Dominating-Set} has a size $k'$ dominating set}

\subsubsection*{Show \textsc{Dominating-Set} has a size $k'$ dominating set if \textsc{Vertex-Cover} has a size $k$ cover}

\subsubsection*{Conclude that \textsc{Dominating-Set} is NP-hard}

\subsection*{Conclude that \textsc{Dominating-Set} is NP-complete}


\end{empfile}
\immediate\write18{mpost -tex=latex \jobname}
\end{document}
