\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 8 (due Wednesday, April 4th 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.
\bigskip
\hrule
\bigskip
\noindent
For problems that use maximum flows as a black box, a full-credit solution requires the following.
\begin{itemize}
\item
A complete description of the relevant flow network, specifying the set of vertices, the set of edges (being careful about direction), the source and target vertices $s$ and $t$, and the capacity of every edge. (If the flow network is part of the original input, just say that.)
\item
A description of the algorithm to construct this flow network from the stated input. This could be as simple as ``We can construct the flow network in $O(n^3)$ time by brute force.''
\item
A description of the algorithm to extract the answer to the stated problem from the maximum flow. This could be as simple as ``Return \textsc{True} if the maximum flow value is at least $42$ and \text{False} otherwise.''
\item
A proof that your reduction is correct. This proof will almost always have two components. For example, if your algorithm returns a Boolean, you should prove that its \textsc{True} answers are correct and that its \textsc{False} answers are correct. If your algorithm returns a number, you should prove that number is neither too large nor too small.
\item
The running time of the overall algorithm, expressed as a function of the original input parameters, not just the number of vertices and edges in your flow network.
\item
You may assume that maximum flows can be computed in $O(VE)$ time. Minimum-cost flows can be computed in $O(E^2\log^2{V})$ time. Do \emph{not} regurgitate the maximum flow algorithm itself.
\end{itemize}
Reductions to other flow-based algorithms described in class or in the notes (for example: edge-disjoint paths, maximum bipartite matching, minimum-cost circulation) or to other standard graph problems (for example: reachability, minimum spanning tree, shortest paths) have similar requirements.
\bigskip
\hrule
\bigskip
\newpage
\begin{enumerate}
%----------------------------------------------------------------------
\item The Computer Science Department at UIUC has $n$ professors. They
handle department duties by taking part in various committees. There
are $m$ committees and the $j$'th committee requires $k_j$
professors. The head of the department asked each professor to
volunteer for a set of committees. Let $S_i \subseteq \{1, 2,
\ldots, m\}$ be the set of committees that professor $i$ has
volunteered for. A committee assignment consists of sets $S'_1,
S'_2, \ldots, S'_n$ where $S'_i \subseteq \{1,2, \ldots, m\}$ is the
set of committees that professor $i$ will participate in. A {\em
valid} committee assignment has to satisfy two constraints: (i)
for each professor $i$, $S'_i \subseteq S_i$, that is each professor
is only given committees that he/she has volunteered for, and (ii)
each committee $j$ has $k_j$ professors assigned to it, or in other
words $j$ occurs in at least $k_j$ of the sets $S'_1, S'_2, \ldots,
S'_n$.
\begin{enumerate}
\item {\bf Not to submit:} Describe a polynomial time
algorithm that the head of the department can employ to
check if there is a valid committee assignment given $m$,
$k_1,k_2,\ldots,k_m$ the requirements for the committees,
and the lists $S_1, S_2, \ldots, S_n$. The algorithm should
output a valid assignment if there is one.
\item The head of the department notices that often there is no
valid committee assignment because professors naturally are
inclined to volunteer for as few committees as possible. To
overcome this, the definition of a valid assignment is relaxed
as follows. Let $\ell$ be some integer. An assignment $S'_1,
S'_2, \ldots, S'_n$ is now said to be valid if (i) $|S'_i -
S_i| \le \ell$ and (ii) each committee $j$ has $k_j$
professors assigned to it. The new condition (i) means that a
professor $i$ may be assigned up to $\ell$ committees not on
the list $S_i$ that he/she volunteered for. Describe an
algorithm to check if there is a valid committee assignment
with the relaxed definition.
\end{enumerate}
\item Let $G=(V,E)$ be a {\em directed} graph and let $\mathcal{C} = \{C_1,C_2,\ldots,C_h\}$ be a collection of cycles in $G$. We say that $\mathcal{C}$ is
a {\em cycle partition} of $G$ if each vertex of $V$ is in exactly one
of the cycles. In other words the cycles of $\mathcal{C}$ are vertex disjoint
and together contain all vertices. Describe an algorithm that given
$G$ decides whether $G$ contains a cycle partition. Follow the two steps below.
\begin{enumerate}
\item Argue that a set of edges $E' \subseteq E$ forms a cycle partition
if and only if each vertex $v$ has exactly one incoming edge and
one outgoing edge in $E'$.
\item Use bipartite matching to check if there is an $E' \subseteq E$
satisfying the property in the previous part.
\end{enumerate}
\item Suppose we are given an $n\times n$ grid, some of whose cells
are marked; the grid is represented by an array $M[1 .. n,1 .. n]$
of booleans, where $M[i, j] = \text{True}$ if and only if cell $(i, j)$ is
marked. A monotone path through the grid starts at the top-left
cell, moves only right or down at each step, and ends at the
bottom-right cell. Our goal is to cover the marked cells with as few
monotone paths as possible.
\begin{figure}[h]
\centering
\includegraphics[width=5in]{monotone-paths.pdf}
\end{figure}
\begin{itemize}
\item {\bf Not to submit:}
Describe an algorithm to find a monotone path that covers the
largest number of marked cells.
\item {\bf Not to submit:} There is a natural greedy heuristic to
find a small cover by monotone paths: If there are any marked
cells, find a monotone path $\Pi$ that covers the largest number of
marked cells, unmark any marked cells covered by $\Pi$,
and recurse. Show that this algorithm does {\em not} always compute an
optimal solution.
\item Describe and analyze an efficient algorithm to compute the
smallest set of monotone paths that covers every marked cell.
\end{itemize}
\end{enumerate}
\vspace{1in}
{\bf The remaining problems are for self study. Do \emph{NOT} submit for grading.}
\begin{itemize}
\item See Problem 3 in HW 6 and all problems in HW 7 from Jeff's home work
last spring. \url{https://courses.engr.illinois.edu/cs473/sp2016/hw/hw7.pdf}
\item Klenberg-Tardos Chapter 7 is an excellent source on network flow and
has many nice problems starting with basic ones to advanced ones. There are
several nice problems on reductions to network flow.
\item Jeff's notes on network flow applications also has a good collection
or problems.
\end{itemize}
\end{document}