%Do not change 
\documentclass[12pt, oneside]{article}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{amssymb,amsmath}
\usepackage[margin=1in]{geometry}
\usepackage{textpos}
\usepackage{tikz}
\usepackage{mathtools}
\usepackage{xspace}
\usepackage[mathscr]{euscript}
\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}


\begin{document}
% Do not modify 


%Do not modify other than putting your name, Purdue ID and names of collaborators where stated
\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*}


%Do not modify other than putting your name where stated
\begin{textblock*}{8cm}(12.5cm,-1cm)
%\noindent {Name: } 
\end{textblock*}
%Do not modify other than typing your acknowledgement where stated
\begin{textblock*}{13.5cm}(-1.7cm,-1.8cm)
\noindent \textit{\footnotesize  } 
\end{textblock*}

\vspace{1cm}

%Do not modify other than typing the homework number after #
\begin{center}
\textbf{\Large Homework 6} \\ 
\textbf{Due Date: April 23, 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} 
Given a graph $G$ a triangle consists of a triple $\{u,v,w\}$ such that all three edges $\{u,v\},\{v,w\},\{u,w\} \in E(G)$ are in the graph. Let $T(G) = \{ \{u,v,w\}~:~\{u,v\},\{v,w\},\{u,w\} \in E(G) \}$ denote the set of all triangles in $G$. We say that a subset $S \subseteq V(G)$ is a triangle cover if for each triangle $t = \{u,v,w\} \in T(G)$ we have $t \cap S \neq \emptyset$ i.e., $S$ contains {\em at least} one of the three nodes $u,v,w$. In the weighted version of the triangle cover problem we have a weight $\mathtt{w}(v) \geq 0$ associated with each node $v$ and we define $\mathtt{w}(S) \doteq \sum_{v \in S} \mathtt{w}(v)$. The goal is find a triangle cover with minimum weight.

\begin{enumerate}

\item Consider the unweighted version of the problem in which $\mathtt{w}(v) = 1$ for every node $v$. Find an algorithm that runs in time $T(n,k) = O\left( 3^k \times n^{10} \right)$ where $k$ is the size of the minimum triangle cover. ({\bf Note:} You might find a solution that is faster than the given bound. The key requirement is that the dependence on $n$ must be polynomial). 

\item Find a $3$-approximation algorithm for the weighted triangle cover problem. Your algorithm should run in polynomial time and should output a triangle cover $S$ with the guarantee that $\mathtt{w}(S) \leq 3 \times \mathtt{w}(S^*)$ where $S^*$ denotes the optimal triangle cover.  

\end{enumerate}

 \subsection*{Question 2} The Geography on Graphs Game is defined as follows: Given a directed graph $G = (V, E)$ and a start node $s$, two players alternate turns by following, if possible, an edge out of the current node to an unvisited node. The player who loses is the first one who cannot move to a node that hasn’t been visited earlier. In other words, a player loses if it is his turn, the game is currently at node $v$ and for each directed edges of the form $(v,w) \in E$ the node w has already been visited. The Tripartite Geography on Graphs Game is defined in the same way except that the input graph $G$ must satisfy the property that the nodes $V(G)$ can be partitioned into sets $A,B,C$ and $E(G) \subseteq (A \times B) \cup (C \times A) \cup  (B \times C)$ i.e. any edge starting at $A$ ends in $B$, any edge starting in $B$ ends in $C$ and any edge starting in $C$ ends in $A$. The decision version of the problem is to decide whether or not player 1 can force a win with optimal play.
\begin{enumerate}
\item Suppose that the graph $G$ has no directed cycles. Show that the Geography on a Graph decision problem is solvable in polynomial time. 
\item	Prove that the Tripartite Geography on Graph decision problem  is PSPACE-Complete. You may assume that the regular Geography on Graphs Game is PSPACE-Hard.
\end{enumerate}

  \subsection*{Question 3} It is NP-Hard to find a 3-coloring of a $G$ (or determine that no 3-coloring exists).  In this problem we will design an polynomial time algorithm that is {\em guaranteed} to either output a legal $4\sqrt{n}$-coloring of the graph $G$ or determine that $G$ is not 3-colorable. 
  \begin{enumerate}
	\item (Warmup) Begin by showing that any graph with
		maximum degree $d$ can be colored using $d+1$ colors. 	\emph{(Hint: Go Greedy!)} 
		
		\item Let $v$ denote a vertex in $G$ with $deg(v) \geq \sqrt n$. Call $v$
		a heavy vertex. Show that it is either the case that (1) the subgraph $G[N(v)]$ induced on $N(v) = \{u: u \text{ is adjacent to } v\}$ is bipartite, or (2) the graph $G$ is not 3-colorable.
		
		\item Using the previous observation develop an algorithm which outputs a $4\sqrt{n}$-coloring (or determines that $G$ is not 3-colorable). \emph{(Hint: As a first step try to eliminate all heavy vertices.)} 
  \item [Bonus (5 points)] Extend the previous ideas to design an polynomial time algorithm which is   {\em guaranteed} to either output a legal $O\left(n^{1-1/k}\right)$-coloring of the graph $G$ or determine that $G$ is not k-colorable for any constant $k = O(1)$. 
\end{enumerate}

\subsection*{Question 4}

The difficulty in 3-SAT comes from the fact that there are $2^n$ possible assignments to the input variables $x_1, x_2, \ldots, x_n$, and there's no apparent way to search this space in polynomial time. This intuitive picture, however, might create the misleading impression that the fastest algorithms for 3-SAT actually require time $2^n$. In fact, though it's somewhat counterintuitive when you first hear it, there are algorithms for 3-SAT that run in significantly less than $2^n$ time in the worst case; in other words, they determine whether there's a satisfying assignment in less time than it would take to enumerate all possible settings of the variables. 

Here we’ll develop one such algorithm, which solves instances of 3-SAT in $O(p(n)\cdot (\sqrt{3})^n)$ time for some polynomial $p(n)$. Note that the main
term in this running time is $(\sqrt{3})^n$, which is bounded by $1.74^n$.

\begin{description}
\item{(a)} For a truth assignment $\Phi$ for the variables $x_1, x_2, \ldots, x_n$, we use $\Phi(x_i)$ to denote the value assigned by $\Phi$ to $x_i$. (This can be either 0 or 1.) If $\Phi$ and $\Phi'$ are each truth assignments, we define the distance between $\Phi$ and $\Phi'$ to be the number of variables $x_i$ for which they assign different values, and we denote this distance by $d(\Phi, \Phi')$. In other words, $d(\Phi, \Phi') =|\{i: \Phi(x_i) \neq \Phi'(x_i)\}|$.

A basic building block for our algorithm will be the ability to answer the following kind of question: Given a truth assignment $\Phi$ and a distance $d$, we'd like to know whether there exists a satisfying assignment $\Phi'$ such that the distance from $\Phi$ to $\Phi'$ is at most d. Consider the following algorithm, $Explore(\Phi, d)$, that attempts to answer this question.


\begin{algorithm} % enter the algorithm environment
\caption{Explore($\Phi, d$)} % give the algorithm a caption
\label{alg2} % and a label for \ref{} commands later in the document
\begin{algorithmic}[1] % enter the algorithmic environment
\IF {$\Phi$ is a satisfying assignment}
	\RETURN {``yes''}
\ELSIF {if d = 0}
	\RETURN {``no''}
\ELSE
	\STATE Let $C_i$ be a clause that is not satisfied by $\Phi$ (i.e., all three terms in $C_i$ evaluate to false)
    \STATE Let $\Phi_1$ denote the assignment obtained from $\Phi$ by taking the variable that occurs in the first term of clause $C_i$ and inverting its assigned value
    \STATE Define $\Phi_2$ and $\Phi_3$ analogously in terms of the second and third terms of the clause $C_i$
    \STATE Recursively invoke: $Explore(\Phi_1,d-1), Explore(\Phi_2,d-1), Explore(\Phi_3,d-1)$
	\IF {any of these three calls return ``yes''}
    	\RETURN {``yes''}
    \ELSE
		\RETURN {``no''}
    \ENDIF
\ENDIF
\end{algorithmic}
\end{algorithm}

Prove that $Explore(\Phi, d)$ returns ``yes'' if and only if there exists a satisfying assignment $\Phi'$ such that the distance from $\Phi$ to $\Phi'$ is at most d. Also, give an analysis of the running time of $Explore(\Phi, d)$ as a function of $n$ and $d$.

\item{(b)} Clearly any two assignments $\Phi$ and $\Phi'$ have distance at most $n$ from each other, so one way to solve the given instance of 3-SAT would be to pick an arbitrary starting assignment $\Phi$ and then run $Explore(\Phi, n)$. However, this will not give us the running time we want.

Instead, we will need to make several calls to $Explore$, from different starting points $\Phi$, and search each time out to more limited distances. Describe how to do this in such a way that you can solve the instance of 3-SAT in a running time of only $O(p(n)\cdot(\sqrt{3})^n)$.
\end{description}



\subsection*{Bonus (10 points)} 
The {\sf Hitting Set} problem is similar to the {\sf Set Cover} problem. An instance is given by a list $S_1,\ldots,S_n \subseteq {1,…,m}=U$ of $n$ subsets of a universe $U$ of size $|U|=m$. In the {\sf Set Cover} problem we want to find a minimum size subset of sets $S \subseteq {1,…,n}$ which covers the universe $U$ i.e., $\bigcup_{i \in S} S_i = U$. In the {\sf Hitting Set} problem we are given an absolute upper bound $k$ on the number of sets in $S$ and we are asked to {\em maximize} the number of elements covered by $S$ i.e., $ \left| \mathtt{Covered}(S) \right|$ where $\mathtt{Covered}(S) =\bigcup_{i \in S} S_i $. In the {\sf Weighted Hitting Set} problem there is a weight $\mathtt{w}(u)$ for each item $u \in U$ we are asked to find $S$ with $|S| \leq k$ maximizing $\mathtt{score}(S) = \sum_{x \in \mathtt{Covered}(S) } \mathtt{w}(x)$. The search version of the {\sf Weighted Hitting Set} problem is {\sf NP-Hard} (you don’t need to prove this).  

\begin{enumerate}
\item Let $V^* = \mathtt{Covered}(S^*)$ denote the items covered by the optimal solution the {\sf Weighted Hitting Set} problem$|S^*| \leq k$. Given another hitting set solution $P \subseteq \{1,\ldots,n\}$ we define $\mathbf{Uncovered}(V^*,P) \doteq V^* \setminus \mathtt{Covered}(P)$ to be the set of items covered by $S^*$ but not by $P$. We let  $uw_P = \sum_{x \in \mathbf{ Uncovered}(V^*,P)} \mathtt{w}(x)$ denote the total weight of uncovered elements in $V^*$. Show that for any subset  $P \subsetneq \{1,\ldots ,n\}$ there exists some $j \not \in P$ s.t. $\sum_{i \in S_j \cap \mathbf{Uncovered}(V^*,P)} \mathtt{w}(i) \geq \frac{uw_P}{k}$.
\item	Develop a greedy algorithm that always returns a weighted hitting set solution $S$ such that $\mathtt{score}(S) \geq (1-1/e) \times \mathtt{score}(S^*)$. ({\bf Hint:} Go greedy! You may use without proof the fact that $(1-1/k)^{k}   <= e^{-1}$ for all integers $k,x>0$.  )
\end{enumerate}

\end{document}