\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, Monday Week 7}
}
\renewcommand{\headrulewidth}{0pt}
}

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

\begin{prob}
  Sipser described a polynomial time reduction of~3SAT to CLIQUE.
  \begin{enumerate}
    \item 
      \begin{enumerate}[(i)]
	\item Use the same idea to associate a graph to the boolean formula
	  $\phi=(x\vee y)\wedge(\overline{x}\vee z)\wedge(y\vee \overline{z})$
	  so that the solutions in the formula correspond to $3$-cliques in the
	  graph.  
	\item Give some specific examples of solutions and their corresponding
	  cliques.
      \end{enumerate}
    \item Suppose you are given a 3SAT problem with~$k$ clauses.  Construct the
      corresponding graph as described by Sipser.  Is it possible for the graph
      to have a clique of size larger than~$k$.  Give a proof that
      is it not possible, or give an explicit example showing that it is
      possible.
  \end{enumerate}
\end{prob}

\begin{prob}
  An undirected finite graph is \emph{$3$-colorable} if there is a way to assign one of three different
  colors to each of its vertices in such a way the no two adjacent vertices have
  the same color.  Let
  \[
    \text{3COLOR} = \{\langle G\rangle: \text{$G$ is a $3$-colorable graph}\}.
  \]
  In this problem, you are asked to give a polynomial time reduction of 3SAT to 3COLOR in order to show that
  3COLOR is NP-complete. 
  \medskip

  To describe the reduction, let the colors be True, False, and Blank.
  Take one vertex for each literal~$x_{i}$ and one for its negation $\overline{x}_{i}$.
  We do not want both $x_{i}$ and $\overline{x}_{i}$ to both be assigned True
  or both be assigned False.  So add edges:
  \medskip

  \begin{center}
    \begin{tikzpicture}
      \node[ball,label={below:$x_{i}$}] (t) at (0,0) {};
      \node[ball,label={below:$\overline{x}_{i}$}] (f) at (1,0) {};
      \draw (t)--(f);
    \end{tikzpicture}
  \end{center}

  To make sure that no vertex corresponding to a literal is colored Blank, add
  the following triangle to the graph:

  \begin{center}
    \begin{tikzpicture}[scale=0.7]
      \node[ball,label={left:$T$}] (t) at (0,0) {};
      \node[ball,label={right:$B$}] (b) at (2,0) {};
      \node[ball,label={above:$F$}] (f) at (1,1.732) {};
      \draw (t)--(b)--(f)--(t);
    \end{tikzpicture}
  \end{center}
  The vertices are labeled $T$, $F$, and~$B$, as shown.  (These are labels, not
  the colors True, False, Blank. However, given any~$3$-coloring, we can permute the
  colors to get another $3$-coloring such that~$T,F,B$ are colored True, False,
  Blank, respectively).  Now connect vertices representing literals to
  the vertex of the triangle labeled $B$.

  The following structure serves as an ``OR-gadget'':
  \begin{center}
    \begin{tikzpicture}[scale=0.5]
      \node[ball] (t) at (1,1.732) {};
      \node[ball] (l1) at (0,0) {};
      \node[ball] (r1) at (2,0) {};
      \node[ball] (l2) at (0,-1.732) {};
      \node[ball] (r2) at (2,-1.732) {};
      \draw (t)--(l1);
      \draw (t)--(r1);
      \draw (l1)--(r1);
      \draw (l1)--(l2);
      \draw (r1)--(r2);
    \end{tikzpicture}
  \end{center}
  By adding two edges from the top vertex of the gadget: one to vertex~$B$ and
  one to vertex~$F$, we can assure that in any $3$-coloring, the top vertex will
  have the same color as vertex~$T$.
  \medskip

  \begin{enumerate}
      \item Use the pieces above to create a graph corresponding to the
	clause~$x\vee \overline{y}$ in the variables $x$ and~$y$.
      \item Use the pieces above to create a graph corresponding to the
	clause~$x\vee \overline{y}\vee z$ in the variables $x,y$ and~$z$.
      \item Describe the construction for a general formula in 3SAT.
  \end{enumerate}
\end{prob}

\begin{prob} (bonus) Let~$f_{1},\ldots,f_{m}$ be a list of final exams, and let
  $s_{1},\ldots,s_{n}$ be a list of students.  Each student takes some specified
  subset of the final exams. Each final exam is a single time slot in length. The
  problem is to determine if these finals can be scheduled in only $h$
  non-overlapping time slots so that no student has two simultaneous exams.
  Show that this scheduling problem is NP-complete.
\end{prob}
\end{document}
