\documentclass[11pt]{article}
	\usepackage[margin=1in]{geometry}
	\usepackage{amsfonts, amsmath, amssymb, amsthm}
	\usepackage{microtype}
	\usepackage{nicefrac}
	\usepackage[small]{complexity}

	\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}
	}

	% complexity, needs to be after hyperref to work
		\renewcommand{\S}{\defaultS}
		\renewcommand{\L}{\ComplexityFont{L}}
		\newcommand{\ETIME}{\ComplexityFont{E}}

	\newcommand{\thecourse}{\errmessage{Course is undefined}}
	\newcommand{\handout}[5]{
		%\renewcommand{\thepage}{#1-\arabic{page}}
		\noindent%
		\begin{center}%
			\framebox{%
				\vbox{%
					\vspace{1mm}%
					\hbox to 5.78in {
						{\bf \thecourse}%
						\hfill%
						\smash{\parbox[t]{3in}{\raggedleft #2}}%
					}%
					\vspace{\baselineskip}%
					\hbox to 5.78in { {\Large \hfill #5  \hfill} }%
					\vspace{\baselineskip}%
					\hbox to 5.78in {%
						\smash{\parbox[b]{2.5in}{\raggedright #3}}%
						\hfill
						\smash{\parbox[b]{3in}{\raggedleft #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{\F}{\mathbb{F}}
	\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}
	\DeclareMathOperator{\Var}{Var}

	\renewcommand{\E}{\mathbb{E}}

	%	open/closed intervals
	%       [
	\newcommand{\ocint}[2]{\ensuremath{(#1,#2]}}%)
	\newcommand{\icint}[1]{\ocint{\infty}{#1}}
	%       (
	\newcommand{\coint}[2]{\ensuremath{[#1,#2)}}%]
	\newcommand{\ciint}[1]{\coint{#1}{\infty}}
	\newcommand{\ccint}[2]{\ensuremath{[#1,#2]}}%)
	\newcommand{\ooint}[2]{\ensuremath{(#1,#2)}}%)

	% 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}

\renewcommand{\thecourse}{cs473 Algorithms}
\handout{0}%
	{}%
	{Prof.\ Michael A. Forbes}%
	{Due: \textit{Thu., 2026-03-12 21:00}}%
	{Problem Set \#4}

Submissions must obey the following guidelines when using \emph{reductions} to solve problems, in particular when using algorithms for computing maximum flows as a black-box.

\begin{itemize}

	\item \emph{Construction:}  Submissions must completely describe the relevant capacitated graph by describing the vertices, the edges (with direction), and capacities.  The source $s$ and sink $t$ must also be identified.

	\item \emph{Forward reduction:}  Submissions must describe an algorithm to, given the original input, construct the above mentioned capacitated graph.  This includes a correctness and complexity analysis.

	\item \emph{Backwards reduction:}  Submissions must describe an algorithm to, given a maximum flow in the constructed capacitated graph, efficiently solve the original problem.  This includes a correctness and complexity analysis.  An argument for correctness will typically require two directions.  First, if the resulting maximum flow is \emph{large} in value, then the produced solution to the original problem is correct.  Second, if the resulting maximum flow is \emph{small} in value, then the produced solution to the original problem is correct.

	\item \emph{Complexity:}  The overall complexity of the entire algorithm must be specified as a function of the \emph{original} input (\textbf{not} as a function of the constructed capacitated graph).

	\item Submissions should assume that maximum flows can be computed in $O(nm)$ time on graphs with $n$ vertices and $m$ edges, and in particular should \textbf{not} reproduce a maximum flow algorithm unless required.
		
\end{itemize}

Analogous guidelines exist for reductions to other problems whose algorithms were presented in lecture or auxiliary reading, such as shortest paths with negative edge lengths, or maximum bipartite matching.

All problems are of equal value.

\begin{enumerate}

	\item Decreasing the flow.  Kleinberg-Tardos Chapter 7, Problem \#12.

	\item Disaster allocation.  Kleinberg-Tardos Chapter 7, Problem \#9.

	\item Give an analysis (correctness and complexity) of the following algorithm for maximum flow, expressing the runtime in terms of the number of vertices $n$, edges $m$, and sum of capacities $F=\sum_e c_e$.

		\fcode
		{
			{\bf rounding-FF}($G=(V,E),(c_e)_{e\in E}$):\\
			\>	if all capacities zero, return the zero flow\\
			\>	define capacities $c'$ by $(c')_e=\floor{c_e/2}$, for $e\in E$.\\
			\>	recursively compute $f=${\bf rounding-FF}($G$,$c'$)\\
			\>	$f_e\leftarrow 2\cdot f_e$ for $e\in E$.\\
			\>	initialize the residual graph $G^f$\\
			\>	while exists $s\leadsto t$ path $p$ in $G^f$\\
			\>	\>	augment $f\leftarrow f+p$\\
			\>	\>	update $G^f\leftarrow G^{f+p}$\\
			\>	return $f$
		}

\end{enumerate}

\end{document}
