\documentclass[11pt]{amsart}

\usepackage{amsmath,amsthm,amssymb}
\usepackage{stmaryrd}

\usepackage{fancyhdr} % Allows customization of verbatim environments

\usepackage{xcolor}

%\usepackage[textheight=8.5in, margin=1.6in]{geometry}
\usepackage[
  hmarginratio={1:1},     % equal left and right margins
%  vmarginratio={1:1},     % equal top and bottom margins
  %textwidth=400pt,        % new text width
  heightrounded,          % always useful
  %bindingcorrection=5mm,  % binding correction
  total={6in,8in}
]{geometry}
\headheight=13pt
\footskip=13pt

\usepackage{needspace}  % <-- to prevent bad pagebreak over environment titles
% Use:  \Needspace{3\baselineskip} before opening an environment

\usepackage{graphicx}

% Tikz stuff.
\usepackage{tikz}
%\usepackage{tkz-graph}
\usepackage{pgfplots}
%\usepackage{tikz-3dplot}
\pgfplotsset{compat=newest}
%\usepgfplotslibrary{fillbetween}
%\usetikzlibrary{cd}
%\usetikzlibrary{positioning}
%\usetikzlibrary{decorations.pathmorphing}    
%\usetikzlibrary{decorations.pathreplacing}
%\usetikzlibrary{arrows.meta,calc}
%\usetikzlibrary{bending}
%\usetikzlibrary{decorations.markings,shapes.geometric}
%\tikzset{->-/.style={decoration={markings, mark=at position #1 with
%  {\arrow{>}}},postaction={decorate}}}
%\tikzset{-|-/.style={decoration={markings, mark=at position #1 with
%  {\arrow{stealth}}},postaction={decorate}}}
%\tikzset{movearrow/.style 2 args ={
%        decoration={markings,
%	  mark= at position {#1} with {\arrow{#2}} ,
%        },
%        postaction={decorate}
%    }
%}
%\tikzset{<--/.style={decoration={markings, mark=at position #1 with
%  {\arrow{<}}},postaction={decorate}}}
\tikzstyle{ball} = [circle,shading=ball, ball color=black,
    minimum size=1mm,inner sep=1.3pt]
%\tikzstyle{bball} = [circle,shading=ball, ball color=blue,
%    minimum size=1mm,inner sep=1.3pt]
%\tikzstyle{miniball} = [circle,shading=ball, ball color=black,
%    minimum size=1mm,inner sep=0.5pt]
%\tikzstyle{redminiball} = [circle,shading=ball, ball color=red,
%    minimum size=1mm,inner sep=0.5pt]
%\tikzstyle{mminiball} = [circle,shading=ball, ball color=black,
%    minimum size=0.6mm,inner sep=0.1pt]
%\tikzstyle{mycircle} = [draw,circle, minimum size=1mm,inner sep=1.3pt]
%\newcommand*{\DashedArrow}[1][]{\mathbin{\tikz [baseline=-0.25ex,-latex, dashed,#1] \draw [#1] (0pt,0.5ex) -- (1.3em,0.5ex);}}%

%%%% tikz style for finite automata
\usetikzlibrary{automata, positioning, arrows}
\tikzset{fa/.style={
    ->, % makes the edges directed
    >=stealth, % makes the arrow heads bold
    node distance=3cm, % specifies the minimum distance between two nodes. Change if necessary.
    every state/.style={thick, fill=gray!10}, % sets the properties for each ’state’ node
    initial text=$ $, % sets the text that appears on the start arrow
}}
%%%%

\usepackage{needspace}  % <-- to prevent bad pagebreak over environment titles
% Use:  \Needspace{3\baselineskip} before opening an environment

\usepackage[shortlabels]{enumitem}
\setlist[enumerate]{itemsep=4pt,leftmargin=*,label={(\alph*)}}
%\setlist[enumerate]{itemsep=2pt,label={\arabic*.}}

\usepackage[T1]{fontenc}
\renewcommand{\labelitemi}{\guillemotright}

\allowdisplaybreaks

\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\W}{\mathbb{W}}
\newcommand{\KK}{\Bbbk}
\newcommand{\ve}{\varepsilon}
\newcommand{\scribe}{
  \begin{center}%
    Scribe~$=$ \rule{7cm}{0.15mm}%
  \end{center}%
  \medskip%
}
\DeclareMathOperator{\im}{\mathrm{im}}
\DeclareMathOperator{\id}{\mathrm{id}}
\DeclareMathOperator{\glb}{\mathrm{glb}}
\DeclareMathOperator{\lub}{\mathrm{lub}}

\newcounter{problem}
\renewcommand \thesection {\theproblem}
\newenvironment{prob}[1][]
{
\refstepcounter{problem}\par\medskip
\def\myArg{#1}
  \ifx\myArg\empty
    \noindent \textsc{Problem~\theproblem.} \rmfamily
  \else
    \noindent \textsc{Problem~\theproblem\ (\textnormal{#1}).} \rmfamily
  \fi
}
{
\medskip

}

\newenvironment{sol}
{\emph{Solution.}
}
{
  \medskip

}

\parskip = 0.05in
\parindent = 0.0in

%\pagestyle{empty}
%\pagenumbering{gobble}

\fancypagestyle{firststyle}
{
\fancyhead[L,LO]{
\textit{\small Math 387 Group problems, Wednesday Week 7}
}
\renewcommand{\headrulewidth}{0pt}
}

\begin{document}
\thispagestyle{firststyle}
\bigskip

\begin{prob} 
  Let $G$ be a simple undirected graph.  A \emph{vertex cover} of~$G$ is a set
  of vertices of~$G$ such that each edge of~$G$ contains at least one vertex
  from the set.  A \emph{minimal vertex cover} is a vertex cover of minimum
  cardinality. Define the language
  \[
    \text{VCOVER} = \{\langle G, m\rangle: \text{$G$ is a graph which has a vertex
    cover of size~$m$}\}.
  \]
  \begin{enumerate}
    \item Let~$n\geq 2$. Find a minimal vertex cover for the complete graph~$K_{n}$ with
      vertices~$\left(1,\ldots,n\right)$. Prove that your set covers
      and that any smaller set would not.
    \item Let $n\geq 3$. Find a minimal vertex cover for the cycle graph~$C_{n}$ with vertices
      $\{1,\ldots,n\}$ arranged in a cycle. (No explanation necessary.)
    \item Find a minimal vertex cover for following graph (no explanation
      required):
      \begin{center}
        \begin{tikzpicture}
          \node[ball,label={below:$1$}] (1) at (0,0) {};
          \node[ball,label={below:$2$}] (2) at (2,0) {};
          \node[ball,label={left:$3$}] (3) at (0,1) {};
          \node[ball,label={right:$4$}] (4) at (2,1) {};
          \node[ball,label={above:$5$}] (5) at (1,2) {};
          \node[ball,label={above:$6$}] (6) at (2,2) {};
          \node[ball,label={above:$7$}] (7) at (3,2) {};
          \node[ball,label={above:$8$}] (8) at (4,2) {};
          \node[ball,label={above:$9$}] (9) at (5,2) {};

	  \draw (1)--(2)--(4)--(3)--(1);
	  \draw (3)--(5)--(4);
	  \draw (5)--(7)--(8)--(9);
        \end{tikzpicture}
      \end{center}
    \item Find a minimal vertex cover for following graph (no explanation
      required):
      \begin{center}
        \begin{tikzpicture}
          \node[ball,label={left:$1$}] (1) at (0,0) {};
          \node[ball,label={below:$2$}] (2) at (1,0) {};
          \node[ball,label={above:$3$}] (t1) at (2,1) {};
          \node[ball,label={above:$4$}] (t2) at (3,1) {};
          \node[ball,label={above:$5$}] (t3) at (4,1) {};
          \node[ball,label={below:$6$}] (b1) at (2,-1) {};
          \node[ball,label={below:$7$}] (b2) at (3,-1) {};
          \node[ball,label={below:$8$}] (b3) at (4,-1) {};
          \node[ball,label={below:$9$}] (9) at (5,0) {};
          \node[ball,label={below:$10$}] (10) at (6,0) {};

	  \draw (1)--(2)--(t1)--(t2)--(t3)--(9)--(10);
	  \draw (2)--(b1)--(b2)--(b3)--(9);
	  \draw (t1)--(b2)--(t3);
	  \draw (b1)--(t2)--(b3);
        \end{tikzpicture}
      \end{center}
    \item Show VCOVER is NP-complete by giving a polynomial time reduction to
  CLIQUE.  So given a graph~$G$ and a number $k$, you need to construct
  an instance of VCOVER---a graph $G'$ and a number $m$---so that finding
  $G$ has a $k$-clique if and only if~$G'$ has an $m$-vertex cover. 
  \medskip

  \noindent Hint: Let~$G'$ be the \emph{complement} of~$G$.  This means $G'$ and $G$ have the same
  vertex set~$V$ but $\{u,v\}$ is an edge of~$G'$ if and only if $\{u,v\}$ is not an
  edge of $G$.  Once you have a well-formulated reduction, separate your if and
  only if proof into two parts.
  \medskip

  \noindent Start with some examples!
  \end{enumerate}
\end{prob}

\begin{prob}
  Here is an attempt at a polynomial time reduction of 3SAT to VCOVER.
      The gadgets are 
      hinted at below. The goal is to create graph that has a minimal vertex
      cover of a certain size if and only if its corresponding 3SAT formula is
      satisfiable.
      \begin{center}
        \begin{tikzpicture}
          \node[circle, draw, inner sep=1pt] (1) at (0,0) {$X_{1}$};
          \node[circle, draw, inner sep=1pt] (2) at (1,1.73) {$\overline{X}_{4}$};
          \node[circle, draw, inner sep=1pt] (3) at (2,0) {$X_{5}$};

	  \draw (1)--(2)--(3)--(1);
	  \node at (1,-1) {clause gadget};
	  \begin{scope}[xshift=6cm]
	    \node[circle, draw, inner sep=1pt] at (0,0) (1) {$x_{5}$};
	    \node[circle, draw, inner sep=1pt] at (2,0) (2) {$\overline{x}_{5}$};
	    \draw (1)--(2);
	    \node at (1,-1) {variable gadget};
	  \end{scope}
        \end{tikzpicture}
      \end{center}
      \begin{enumerate}
        \item Encode the clause $x_{1}\vee\overline{x}_{4}\vee x_{5}$ as a
	  graph using $9$ vertices.  
	\item What is the size of a minimal vertex cover of your graph?
        \item Encode the clause $(x_{1}\vee\overline{x}_{4}\vee
	  x_{5})\wedge(x_{2}\vee x_{4}\vee x_{5})$ as a
	  graph using~$14$ vertices.  
	\item What is the size of a minimal vertex cover of your graph?
	\item A general 3SAT formula~$\phi$ may be encoded as an instance of the
	  minimal vertex color problem by generalizing the above construction.
	  You do not need to describe it here.  However, answer this: if~$\phi$
	  has $k$
	  clauses, and the total number of variables appearing in~$\phi$
	  is~$\ell$, what is the size of a minimal vertex color in the case the
	  formula is satisfiable? (A variable has the form $x_{i}$, and we count
	  it as appearing in~$\phi$ if it or its negation, $\overline{x}_{i}$ is
	  in any clause of~$\phi$.  Thus, for instance, the total number of
	  variables appearing in $(x_{1}\vee\overline{x}_{4}\vee
	  x_{5})\wedge(x_{2}\vee x_{4}\vee x_{5})$ is $4$.)
	\item Describe how a polynomial time decider for VCOVER would provide a
	  polynomials time decider for 3SAT
      \end{enumerate}
\end{prob}

\end{document}
