\documentclass[12pt, oneside]{article}
\usepackage{amssymb,amsmath}
\usepackage[margin=1in]{geometry}
\usepackage{textpos}
\usepackage{mathtools}
\usepackage{xspace}
\usepackage{hyperref}
\newcommand\myeq{\stackrel{\mathclap{\normalfont\mbox{?}}}{=}}
\newcommand\eq{\stackrel{\mathclap{\normalfont\mbox{def}}}{=}}
% You may add the packages you need here
\newcommand\rd{\textsuperscript{rd}\xspace}
\newcommand\nth{\textsuperscript{th}\xspace}
\newcommand\eps{\varepsilon}
\newcommand\after{{\tt After}}
\newcommand\bool{{\tt Bool}}
\newcommand \experiment{{\tt TheGreatExperiment}}
\newcommand \bY{\boldsymbol{Y}}
\newcommand \nph{{\sf{NP}}-Hard }

\begin{document}
% Do not modify 


%Do not modify other than putting your name where stated and filling in the list of collaborators.
\begin{textblock*}{16cm}(-1.7cm,-2.3cm)
\noindent {\large CS 580-Spring 2019} \\
\noindent {\large Instructor: Jeremiah Blocki} \\
\noindent {\large TAs:  Hamidreza Amini Khorasgani, Akash Kumar} \\
\noindent {\large I collaborated with (...). I affirm that I wrote the solutions in my own words and that I understand the solutions I am submitting.} \\
\noindent {\large Name: } 
\end{textblock*}



\vspace{1cm}

%Do not modify other than typing the homework number after #
\begin{center}
\textbf{\Large Homework 5} \\ 
\textbf{Due Date: March 28, 2019 at 11:59 PM on Gradescope.}%\\
%\textbf{Instructor: Jeremiah Blocki}\\
%\textbf{TAs: Chang Li, Akash Kumar}
\end{center}


%Rest should contain your solution for the homework. Feel free to improvise in ways that you believe make grading easier.
\subsection*{Question 1}
Consider the following two decision problems:

\begin{itemize}
\item[--] OR(G,k): Either $G$ contains no odd length cycle OR $G$ has a vertex cover $S \subseteq V(G)$ of size $|S|  \leq k$.
\item[--] AND(G,k): $G$ contains no odd length cycle AND $G$ has a vertex cover $S \subseteq V(G)$ of size $|S|  \leq k$.
\end{itemize}

One of the problems is NP-Complete and the other one is in P. Your mission -- you better choose to accept it -- is to figure out which of the above problems is NP-Complete. You should prove that your answer is correct by providing a polynomial time algorithm to solve one problem and by proving that the other problem is NP-Complete. 

\subsection*{Question 2} 
A sorted sequence of real numbers is a sequence of the form 
$a_1 \leq a_2 \leq \ldots \leq a_n$. A sequence of real numbers
$b_1, b_2, \ldots b_n$ is said to be $\eps$-close to being sorted 
if there is a sorted sequence $a_1 \leq a_2 \leq \ldots \leq a_n$
such that $\sum |a_i - b_i| \leq \eps$. \\

Of course, you know what a sorted sequence of numbers looks like. 
Unfortunately, your manager at a software development company does not. He has a 
sequence of real numbers $$\bY = y_1, y_2, \ldots y_n$$ which is not
quite sorted which will be fed as an input to \experiment. There 
is some hope that this will not lead to any disaster as long as
the sequence $\bY$ is (pretty darn) $\eps$-close for some tiny 
$\eps > 0$. Use linear programming to determine whether the sequence
$\bY$ is $\eps$-close to being sorted. 


\subsection*{Question 3}
Recall that a 2-SAT Instance $\Phi$ consists of $n$ variables $x_1,\ldots,x_n$ and $m$ clauses $C_1,\ldots,C_m$ where each clause $C_i = \ell_{i_1} \vee \ell_{i_2}$ is the disjunction of two {\em distinct} literals. In this problem you will develop a linear time algorithm to solve the problem by reducing the 2-SAT instance to a directed graph $G_{\Phi}$ defined as follows: \\

\noindent{\bf  Nodes:} For each literal $\ell$ we add a node $v_{\ell}$ ($2n$ nodes total) \\
\noindent{\bf Notation: } Given a node $v_{\ell}$ we use $v_{\overline{\ell}}$ to denote the node corresponding to $\overline{\ell}$. For example if $\ell = \overline{x}$ then $v_{\overline{\ell}} = v_x$. \\
\noindent{\bf Edges:}  For each clause $C = \ell \vee \ell '$ we add two directed edges $\left(v_{\overline{\ell}}, v_{\ell'}\right)$ and  $\left(v_{\overline{\ell'}}, v_{\ell}\right)$. \\

\noindent{\bf Part 0} Suppose that we have a directed path $P = v_{\ell_1},v_{\ell_2},\ldots,v_{\ell_k}$ in $G_{\Phi}$. Explain why $\overline{P} =v_{\overline{\ell}_k},\ldots, ,v_{\overline{\ell}_2},v_{\overline{\ell}_1}$ is a valid directed path in $G_{\Phi}$.  \\

\noindent{\bf Part 1:} Suppose that for some literal $\ell$ there is directed path from node $v_{\ell}$ to $v_{\overline{\ell}}$ in $G_{\Phi}$ {\em and} that there is also a directed path from  $v_{\overline{\ell}}$ to $v_{\ell}$  in $G_{\Phi}$. Show that the 2-SAT instance $\Phi$  is not satisfiable. \\

\noindent{\bf Part 2: } Suppose that for every literal $\ell$ the nodes $v_{\ell}$ and $v_{\overline{\ell}}$ are in separate strongly connected components in $G_{\Phi}$. Show that the 2-SAT instance $\Phi$  is satisfiable. \\

\noindent{\bf Part 3:} Describe an O(n+m) time algorithm which solves the 2-SAT problem. If the 2-SAT formula $\Phi$ is not satisfiable then the algorithm should output “no-solution” otherwise the algorithm should output a satisfying assignment. (Hint: You may use \href{https://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm}{Tarjan's Algorithm} as a blackbox. ). 



\subsection*{Question 4}

So, we are back to city $Z$ which is frequented by villanous monsters. The 
city has started a Hero Association to deal with these troublemakers. There
is a set $V$ of $n$ villains and a set $H$ of $m$ heroes. Each hero 
$h \in H$ is a resource that can be allocated to fight off exactly one
villain. Each villain $v \in V$ has a subset $H_v \subseteq H$ of heroes that
must be assigned to capture $v$. The Hero Association needs you to solve the 
decision problem $ZHERO(n,m,k)$ which asks whether they can allocate the heroes 
to villains such that at least $k$ villains get captured.\\

Let us try to get a feel for how this problem behaves through the
following subparts.

\begin{enumerate}

	\item Assume $k = O(1)$ and $m$ and $n$ are large. Help the Hero Association 
		come up with a polynomial time algorithm to solve $ZHERO(n,m,k)$ in
		this setting. \\


	\item Assume all of $n,m,k$ are all very large. Answer the following questions.
		\begin{enumerate}
			\item Show that $ZHERO(n,m,k)$ is in {\sf NP}.

			\item Show that $ZHERO(n,m,k)$ is \nph by giving a reduction 
				from the matching problem in $3$-uniform hypergraphs. 
				The matching problem in $3$-uniform hypergraphs is as 
				follows: You are given a triple of vertex sets
				$A,B,C$ where $|A| = |B| = |C| = m$. You are told that 
				a subset $E \subseteq A \times B \times C$ form hyperedges 
				each of which span $3$ vertices -- one each from $A$, $B$ 
				and $C$. We want to decide whether there exists a subset 
				$M \subseteq E$ with $|M| \geq k$ where no two hyperedges 
				in $M$ share any vertex.

			\item Assume you have an oracle which solves the decision
				problem $ZHERO(n,m,k)$. Give an algorithm that calls
				this oracle a polynomial number of times and finds
				the biggest subset $S \subseteq V$ of villains that
				can be safely captured.
		\end{enumerate}
		



\end{enumerate}

\end{document}
