\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, Fall 2016}
\\[0.5ex]
\textbf{HW 7 (due Tuesday, October 25th 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. 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 Maxflow-mincut theorem and Menger's theorem(s) allow one to move
between flows and cuts and prove useful and interesting facts
that would otherwise be difficult to show directly. Prove the following.
\begin{itemize}
\item Let $G=(V,E)$ be a directed graph and let $u,v,w$ be distinct
vertices. Suppose there are $k$ edge disjoint paths from $u$ to $v$
in $G$, and $k$ edge disjoint paths from $v$ to $w$ in $G$. Note that
the paths from $u$ to $v$ can share edges with the paths from $v$ to $w$.
Prove that there are $k$ edge disjoint paths from $u$ to $w$ in $G$.
\item {\bf Not to submit:} Suppose $G$ is an Eulerian directed graph. That is, the in-degree
of each vertex is the same as the out-degree of each vertex. Prove
that if there are $k$ edge-disjoint paths from $u$ to $v$ then there
are $k$ edge-disjoint paths from $v$ to $u$.
\item Suppose $G$ is a connected simple {\em undirected} graph. A
vertex $v$ is a cut-vertex if $G-v$ has at least two distinct
connected components. If $G$ has no cut-vertices we say it is a {\em
block} or $2$-node-connected. If $G$ has exactly two vertices
then it is an edge and is a block. Blocks are more
interesting when there are at least $3$ vertices. Prove that in a
block with at least $3$ vertices, every two vertices $u,v$ are in
some cycle. In fact you can use this to prove an even a stronger
statement that every two edges $e_1$ and $e_2$ are in a cycle. Do
you see how?
\end{itemize}
\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{itemize}
\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{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}