\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage{amsfonts, amsmath, amssymb, amsthm}
\usepackage{microtype}
\usepackage{nicefrac}
\usepackage[small]{complexity}
\renewcommand{\S}{\defaultS}
\renewcommand{\L}{\ComplexityFont{L}}
\newcommand{\ETIME}{\ComplexityFont{E}}
\usepackage[colorlinks=true]{hyperref}
\hypersetup{
linkcolor=[rgb]{0.5, 0.2, 0.2},
citecolor=[rgb]{0.2, 0.5, 0.2},
urlcolor =[rgb]{0.2, 0.2, 0.5}
}
\newcommand{\thecourse}{cs473: Algorithms}
\newcommand{\handout}[5]{
%\renewcommand{\thepage}{#1-\arabic{page}}
\noindent%
\begin{center}%
\framebox{%
\vbox{%
\vspace{1mm}%
\hbox to 5.78in { {\bf \thecourse} \hfill #2 }%
\vspace{4mm}%
\hbox to 5.78in { {\Large \hfill #5 \hfill} }%
\vspace{4mm}%
\hbox to 5.78in { {#3 \hfill #4} }%
}%
}%
\end{center}%
\vspace*{4mm}%
}%
\setlength\parindent{0pt}
% https://tex.stackexchange.com/questions/21004/add-asterisk-after-labels-in-enumerate
\newenvironment{starnumerate}{\enumerate\setupstarnumerate}{\endenumerate}
\newif\ifstaritem
\newcommand{\setupstarnumerate}{%
\global\staritemfalse
\let\origmakelabel\makelabel
\def\staritem##1{\global\staritemtrue\def\mesymbol{##1}\item}%
\def\makelabel##1{%
\origmakelabel{##1\ifstaritem\rlap{\mesymbol}\fi\enspace}%
\global\staritemfalse}%
}
% math
\newcommand{\N}{\mathbb{N}}
\newcommand{\bits}{\ensuremath{\{0,1\}}}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\newcommand{\rX}{\mathsf{X}}
\newcommand{\rY}{\mathsf{Y}}
\newcommand{\rZ}{\mathsf{Z}}
\newcommand{\e}{\mathrm{e}}
\renewcommand{\vec}[1]{\overline{#1}}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\newcommand{\eps}{\epsilon}
\renewcommand{\E}{\mathbb{E}}
% copied from 2018-01_cs473-algorithms.lectures.zip/prefix.tex
\newcommand{\fcode}[1]
{
\smallskip
\centerline{
\fbox{
\begin{minipage}{0.95\linewidth}
\code{#1}
\end{minipage}
}
}
\smallskip
}
\newcommand{\innercode}[1]
{
\begin{tabbing}
----\=----\=----\=----\=----\=----\=----\kill
#1
\end{tabbing}
}
\newcommand{\code}[1]
{
\footnotesize
\tt
\begin{center}
\innercode{#1}
\end{center}
}
\begin{document}
\handout{0}{Assigned: \textit{Wed., Oct. 23, 2019}}{\parbox{2in}{Prof.\ Michael A. Forbes\\ Prof.\ Chandra Chekuri}}{Due: \textit{Wed., Oct. 30, 2019 (10:00am)}}{Problem Set \#7}
\bigskip
\hrule
\bigskip
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 \textsc{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 value, 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 max-flows) or to other standard graph problems (for example: reachability, minimum spanning tree, shortest paths) have similar requirements.
\bigskip
\hrule
\bigskip
All (non-optional) problems are of equal value.
\begin{enumerate}
\item The maxflow-mincut theorem and its specializations (e.g., Hall's Theorem, Menger's Theorem) can translate questions between the language of flows to the language of cuts, and vice versa. This can facilitate proving useful and interesting facts that would otherwise be difficult to show directly. Prove the following.
\begin{enumerate}
\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 Suppose $G$ is a connected simple \emph{undirected} graph. A vertex $v$ is a \emph{cut-vertex} if $G-v$ has at least two distinct connected components. If $G$ has no cut-vertices we say it is a \emph{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, that for every two vertices $u,v$ there is a (simple) cycle $C_{u,v}$ containing both $u$ and $v$.
\emph{Note:} One can prove the stronger result that every two edges $e_1$ and $e_2$ are in such a (simple) cycle.
\item (\textbf{optional}, \emph{not} for submission) Suppose $G$ is an Eulerian directed graph, that is, a graph where 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$.
\end{enumerate}
\item The computer science department at UIUC has $n$ professors. They handle departmental duties by taking part in various committees. There are $m$ committees and the $j$-th committee requires at least $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 \emph{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 they have volunteered for, and (ii) each committee $j$ has at least $k_j$ professors assigned to it, that is, $j$ occurs in at least $k_j$ of the sets $S'_1,S'_2,\ldots,S'_n$.
\begin{enumerate}
\item (\textbf{optional}, \emph{not} for submission) Describe a polynomial time algorithm that the head of the department can employ to check if there is a valid committee assignment given $m$, the requirements for the committees $k_1,k_2,\ldots,k_m$, 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\setminus S_i|\le\ell$ and (ii) each committee $j$ has at least $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 they 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 \emph{directed} graph and let $\mathcal{C}=\{C_1,C_2,\ldots,C_k\}$ be a collection of cycles in $G$. We say that $\mathcal{C}$ is a \emph{cycle cover} 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 cover. Follow the two steps below.
\begin{enumerate}
\item Argue that a set of edges $E'\subseteq E$ forms a cycle cover 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}
\end{enumerate}
\end{document}