\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage{amsfonts, amsmath, amssymb, amsthm}
\usepackage{microtype}
\usepackage{nicefrac}
\usepackage{graphicx}
\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}
}
\DeclareMathOperator{\Geom}{\mathsf{Geom}}
\DeclareMathOperator{\Bern}{\mathsf{Bern}}
\DeclareMathOperator{\Var}{Var}
\newcommand{\set}[1]{\{#1\}}
\begin{document}
\handout{0}{\smash{\parbox[t]{2.1in}{\raggedleft Assigned: \textit{Mon., Oct. 26, 2020} }}}{\parbox{2in}{Forbes/Chekuri}}{Due: \textit{Thu., Nov. 5, 2020 (5:00pm)}}{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
\newpage
All 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{itemize}
\item 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$.
\item Suppose $G$ is $d$-regular bipartite graph. Prove that it has
a perfect matching.
\end{itemize}
\item Let $G=(V,E)$ be an undirected graph. Let $V$ be partitioned
into two sets of nodes $R$ and $N$ where $R$ is the set of reliable
nodes and $N$ is the set of non-reliable nodes. The reliable nodes
never fail but non-reliable nodes and edges can fail. Call
$N \cup E$ the \emph{elements}. Given two reliable
nodes $s,t$ describe an algorithm that computes the minimum number
of elements whose failure results in $s$ and $t$ being
disconnected from each other. See Fig~\ref{fig:elem-conn}.
\begin{figure}[htb]
\centering
\includegraphics[height=2in]{elem-conn.pdf}
\caption{Black nodes are reliable. Removing dotted edges and nodes
disconnects $s$ from $t$.}
\label{fig:elem-conn}
\end{figure}
\item Problem 16 in
\href{https://jeffe.cs.illinois.edu/teaching/algorithms/book/11-maxflowapps.pdf}{Chapter
11} of Jeff Erickson's Algorithms book. Only parts (a), (b).
\end{enumerate}
\end{document}