\documentclass[12pt]{article}
\newcommand{\Bonus}[1]{\textbf{[#1 Points OPTIONAL Bonus Problem]}}
\newcommand{\Points}[1]{\textbf{[#1 Points]}}
\newcommand{\Name}[1]{\textbf{#1}}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{fullpage}
% \usepackage{geometry}

\begin{document}
\begin{center}
	\bf
	Algorithms \\
	Computer Science 140 \& Mathematics 168 \\
	Spring 2012 \\
	\rm
	Homework 11a\\
	Due Thursday, April 5
\end{center}

\begin{small}
\noindent \textbf{Note 1:}  On this assignment there are several places where you may need to prove that a problem is NP-complete.  On the last page of this assignment is a list of problems that we have shown to be NP-complete.  You can use any of these in your reductions.  Please do not use a problem that doesn't appear on this list.  \\

\noindent \textbf{Note 2:}  Any NP-completeness proof on this assignment should be quite short.   To give you a sense of the rigor and detail in a ``short proof of NP-completness,'' please refer to the document ``An example of a short proof of NP-completeness''  on the homework web page next to the link for HW 11a. \\

\noindent \textbf{Note 3: }  Takehome Exam 2 will be given out on Tuesday, April 17 and due back on Thursday, April 19.  The exam will cover graph algorithms,
NP-completeness, and approximation algorithms.  Please see the practice problem sheet given out in class today for more details.
\end{small}

\begin{enumerate}

\item  \Points{30} \Name{Three Problems from the Republic of Shmorbodia.}
One of the challenges of an algorithm designer is that it can often unknown whether a given problem can be solved in polynomial time or whether it is NP-complete (or harder!).   This problem is designed to give you a sense of what algorithm designers confront.
First, the gratuitous ``true'' backstory:

You've been hired by the Shmorbodian Proletariat Algorithms Ministry (SPAM) to study three problems of interest to the Republic.
For each of the following problems, your task is to determine if the problem is solvable in polynomial time or is NP-complete.
If you determine that the problem is solvable in polynomial time you must do the following:
\begin{enumerate}
	\item Describe the fastest polynomial time algorithm that you are able to find for that problem.  (You don't have to prove that your algorithm is the fastest possible, but describe the fastest algorithm that you are able to find.  In particular, when applying an existing algorithm that we've seen in class to solve your problem, be sure to choose the fastest such algorithm that applies.)
	\item Derive the running time of your algorithm.
	\item Give a short proof of correctness of your algorithm - \emph{2 or 3 sentences should suffice}.
\end{enumerate}
\textbf{You may use algorithms or theorems that we proved in class or on a homework assignment by simply stating the algorithm or result to which you are appealing.}

If you determine that the problem is NP-complete you must do the following:
\begin{enumerate}
	\item Clearly state \emph{the decision version} of the problem.
	\item Prove that the decision problem is NP-complete using a reduction from a problem that we know to be NP-complete (refer to the list of known NP-complete problems on the back page).
	\item Keep each direction of the ``if and only if'' part of your proof very short  - \emph{2-5 carefully crafted sentences for each direction should suffice}.  Please see the example proof in the document posted alongside this homework set on the course homework page.
\end{enumerate}

\begin{enumerate}

	\item \textbf{Shmorbodian Spanning Trees.}  Shmorbodian Telecom is interested in using minimum spanning trees to construct their phone and data networks.  However, the routers used by Shmorbodian Telecom limit the degree of each node in the spanning tree to 
be no more than some given integer $k$.  The problem here is to find the least cost spanning tree in an undirected weighted graph subject to the constraint  that the maximum degree of any node in the selected spanning tree is at most $k$.  That is, among all spanning trees in which each vertex in the spanning tree has degree $k$ or less, find one of least cost.   (Notice that ``degree $k$ or less'' refers to the the degree in the spanning tree, not to the degree in the original graph!)
	
	\item \textbf{Shmorbodian Rural Firestations.}
	  Let $G=(V,E)$ be an undirected graph in which the vertices represent small towns and the edges represent roads between those towns.  Each edge $e$ 
        has a positive integer weight $d(e)$ associated with it, indicating the length of 	that road.  The \emph{distance} between two vertices (towns) in
        a graph is defined to be the length of the shortest weighted path
        between those two vertices.

	Each vertex $v$ also has a positive integer $c(v)$ associated with it, indicating the cost to build a fire station in that town.
         In addition, we are given a positive integer parameter $D$.
	Our objective is to choose a subset of the vertices which will get  firestations such that no town is more than distance $D$ away from a firestation and the total cost
	of the firestations that are built is minimized.
		
	\item \textbf{IVC:  The Official Research Problem of Shmorbodia.}
Recall that a vertex cover in a graph is a subset of the vertices such that every edge has at least one of its two endpoints covered by a
vertex in this subset.  Recall that an independent set in a graph is a subset of the vertices such
that no two vertices in this subset have an edge between them.

Now consider the following problem called Independent Vertex Cover (IVC).   Given a connected graph $G$ and a positive integer
$k$, find a set of exactly $k$ vertices in the graph which is both an independent set
and a vertex cover of the graph or determine that no such set exists.

\end{enumerate}	
\newpage

\begin{center}
A List of Some Known NP-Complete Problems
\end{center}

\footnotesize
\begin{enumerate}
  \item 3SAT:  Given an expression in conjunctive normal form with 3 literals per clause, is it
satisfiable?
  \item Vertex Cover:  Given a graph $G$ and number $k$, is there a vertex cover of size $k$ or less?
  \item Dominating Set:  Give a graph $G$ and number $k$, is there a dominating set of size $k$ or less?
  \item Independent Set:  Given a graph $G$ and number $k$, is there an independent set of size $k$ or
more?
  \item Clique:  Given a graph $G$ and a number $k$, is there a clique of size $k$ or more?
  \item Graph Coloring:  Given an undirected graph and positive integer $k$, is it possible to color the vertices with $k$ or fewer colors so that two adjacent vertices do not have the same color.	
  \item Directed Hamiltonian Path From $s$ to $t$:  Given a directed graph $G$ and vertices $s$ and $t$, is there a
directed Hamiltonian path from $s$ to $t$?
  \item Directed Hamiltonian Path:  Given a directed graph $G$, is there a
directed Hamiltonian path in the graph.
  \item Directed Hamiltonian Cycle:  Given a directed graph $G$, is there a directed Hamiltonian cycle
in the graph?
  \item Undirected Hamiltonian Path From $s$ to $t$:  Given an undirected graph $G$ and vertices $s$ and $t$, is there
an undirected Hamiltonian path with endpoints $s$ and $t$.
  \item Undirected Hamiltonian Path:  Given an undirected graph $G$, is there an undirected Hamiltonian path in the graph.
  \item Undirected Hamiltonian Cycle:  Given an undirected graph $G$, is there an undirected
Hamiltonian cycle in the graph?
  \item Traveling Salesman Problem:  Given a completely connected weighted undirected graph and a
number $k$, does there exist a traveling salesman tour of cost $k$ or less?
  \item Subset Sum:  Given a set $S$ of positive integers and a target integer $k$, does there exist a
subset of $S$ with sum equal to $k$?
  \item Partition:  Given a set $S$ of positive integers, can the integers be partitioned into two
sets $S_1$ and $S_2$ such that the sum of the elements in $S_1$ is equal to the sum of the elements in
$S_2$?
 \item Bin Packing:  Given a multiset $S$ of positive integers ``objects'', a bin capacity $C$ such that $C$ is greater than or equal to the size of the largest
	object, and a target $t$, is it possible to pack all of the objects
	in $S$ into $t$ or fewer bins, each of capacity $C$?

\end{enumerate}


\end{enumerate}

 \end{document}