\documentclass[11pt]{article}
%\usepackage{pstricks,pst-node}
\usepackage{alltt,fullpage,graphics,color,epsfig,amsmath, amssymb}
\usepackage{hyperref}
\usepackage{boxedminipage}
%\newcommand{\edgee}[1]{\begin{math}\stackrel{#1}{\longrightarrow}\end{math}}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\DeclareMathOperator*{\E}{\mathbb{E}}
\newcommand{\eps}{\epsilon}
\begin{document}
\setlength{\parskip}{.1 in}
\begin{center}
\LARGE
\textbf{CS 473: Algorithms, Spring 2018}
\\[0.5ex]
\textbf{HW 10 (due Wednesday, April 25 at 8pm)}
\end{center}
\noindent
This homework contains three problems. {\bf Read the instructions for
submitting homework on the course webpage}.
\noindent {\bf Collaboration Policy:} For this home work, each student
can work in a group with up to three members. Only one solution for
each group needs to be submitted. Follow the submission instructions
carefully.
\hrule
\medskip\noindent
For problems that ask for a (integer) linear-programming formulation of some problem, a full credit solution requires the following components:
\begin{itemize}\itemsep0pt
\item
A list of variables, along with a brief English description of each variable. (Omitting these English descriptions is a Deadly Sin.)
\item
A linear objective function (expressed either as minimization or maximization, whichever is more convenient), along with a brief English description of its meaning.
\item
A sequence of linear inequalities (expressed using $\le$, $=$, or $\ge$, whichever is more appropriate or convenient), along with a brief English description of each constraint.
\item
A proof that your linear programming formulation is correct, meaning that the optimal solution to the original problem can always be obtained from the optimal solution to the linear program. This may be very short.
\end{itemize}
\noindent
It is \textbf{\textit{not}} necessary to express the linear program in canonical form, or even in matrix form. Clarity is much more important than formality.
\medskip
\medskip
\medskip
For problems that ask to prove that a given problem $X$ is NP-hard, a full-credit solution requires the following components:
\begin{itemize}\itemsep0pt
\item
Specify a known {NP}-hard problem $Y$, taken from the problems listed in the notes.
\item
Describe a polynomial-time algorithm for $Y$, using a black-box polynomial-time algorithm for $X$ as a subroutine. Most {NP}-hardness reductions have the following form: Given an arbitrary instance of $Y$, describe how to transform it into an instance of $X$, pass this instance to a black-box algorithm for $X$, and finally, describe how to transform the output of the black-box subroutine to the final output. A cartoon with boxes may be helpful.
\item
Prove that your reduction is correct. As usual, correctness proofs for {NP}-hardness reductions usually have two components (“one for each f”).
\end{itemize}
\hrule
\bigskip
\newpage
\begin{enumerate}
%----------------------------------------------------------------------
\item Suppose you have a set of $n$ machines, and a set of $m$ jobs to run. To activate and run machine $i$ we need to pay a fixed one-time cost of $c_i$, and the cost of running job $j$ on machine $i$, if active, is $r_{ij}$. Furthermore, machine $i$ can handle at most $d_i$ jobs. We would like to decide which machines to activate (run), and assignment of each job to {\em an active machine} such that total cost (machine activation cost plus cost of running all the jobs) is minimized. Write an {\em integer linear programming} formulation for this problem.
%you work at a big distribution company, and you are tasked
%with deciding which facilities the company should open. There are $n$
%possible locations for the facilities and $m$ customers that have to be
%served. For each of the facilities, the company has to pay a cost $c_i$
%to open facility $i$, and for facility $i$ to provide service to customer
%$j$, the company has to pay a cost $g_{ij}$. Write an
%\textit{integer linear program} formulation for the above problem.
\item {\em Valid coloring} of an undirected graph $G=(V,E)$ is an assignment of colors to vertices such that no two vertices connected by an edge have the same color.
%and an integer $k \geq 1$, whether vertices of $G$ can be colored using at most $k$ colors such that for no edge $(u,v)$ both $u$ and $v$ have the same color.
%the task is to decide whether every
%vertex of $G$ can be colored with a single color such that no edge
%$e = \{u, v\}$ has two endpoints of the same color, and the total number
%of colors used is at most $k$.
Suppose you are given access to an oracle $\mathcal{X}$ the $k$-COLOR problem: given as input
an undirected graph $G$ and an integer $k>0$, returns $1$ if $G$ has a valid coloring with at most $k$ colors, and $0$ otherwise.
Assume $O(1)$-time access to the oracle.
%n instance $(G, k)$ of $k$-color, returns $1$ if $G$ has a valid coloring
%with at most $k$ colors, and $0$ otherwise. You are given an undirected graph
%$G = (V, E)$.
\begin{enumerate}
\item Chromatic number of a graph $G$ is the minimum number of colors needed to obtain a valid coloring of $G$. Design an efficient algorithm to find the chromatic number $\chi(G)$ of $G$.
\item Find an actual minimum coloring of the graph. That is, describe an efficient
algorithm that computes a function $\phi : V \to \{1, 2, \cdots, \chi(G)\}$
such that coloring each vertex $u \in V$ with color $\phi(u)$ produces a
valid coloring of $G$.
\end{enumerate}
\item Prove that the following problems are NP-complete:
\begin{enumerate}
\item Given a directed graph
$G = (V, E)$ that is connected, check if it has a {\em simple path} of
length at least $\lceil \frac{|V|}{2}\rceil$. Simple path is a path on which no vertex repeats.
\item The {\em hitting set} problem: Given a set $U$ of $n$ elements, a collection $A_1,\dots,A_m$ of subsets of $U$, and an integer $k$, check if there exists a subset $X\subset U$ such that $|X|\le k$, and for each $i$ from $1$ to $m$, $A_i \cap X\neq \emptyset$.
\end{enumerate}
\end{enumerate}
\vspace{1in}
\newpage
{\bf The remaining problems are for self study. Do \emph{NOT} submit for grading.}
\begin{itemize}
\item Reduce 3-SAT to 5-SAT. How does this generalize
when you want to reduce 3-SAT to $k$-SAT where $k$ is some fixed constant?
This is a useful exercise to understand the reduction from SAT to 3-SAT.
\item Reduce $3$-COLOR to $11$-COLOR, and $11$-COLOR to $3$-SAT. The latter gives a reduction from $11$-COLOR to $3$-COLOR.
\item We briefly discussed in class how to reduce Dominating Set to
Set Cover. Describe a polynomial time reduction from Set Cover to
Dominating Set.
\item An instance of Subset Sum consists of $n$ non-negative integers
$a_1,a_2,\ldots,a_n$ and a target $B$. The goal is to decide if there
is a subset of the $n$ numbers whose sum is exactly $B$. The 2-Partition
problem is the following: given $n$ integers $a_1,a_2,\ldots,a_n$, is
there a subset $S$ such that the sum of the numbers in $S$ is equal
to $\frac{1}{2}\sum_{i=1}^n a_i$. It is easy to see that 2-Partition
reduces to Subset Sum. Do the reverse. Reduce Subset Sum to 2-Partition.
\item See HW 1 from Sariel's course in Fall 2015.
\url{https://courses.engr.illinois.edu/cs473/fa2015/w/hw/hw_01.pdf}.
\item Jeff's notes, Kleinberg-Tardos and Dasgupta etal have several nice
problems on NP-Complete reductions. Skim through several of them to
quickly identify which problem you would use for the reduction.
\item See Jeff's home work 10 from Spring 2016.
last spring. \url{https://courses.engr.illinois.edu/cs473/sp2016/hw/hw10.pdf}
\end{itemize}
\end{document}