\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 6 (due Tuesday, October 18th 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[0.] {\bf Not to submit:} Please do Problems 1 and 2 in Jeff's homework
from last semester \url{https://courses.engr.illinois.edu/cs473/sp2016/hw/hw6.pdf}.
\item[1.] Suppose $f$ is an $s$-$t$ flow in a network $G=(V,E)$ and let
$f'$ be another flow with value larger than that of $f$. Prove that
there is an $s$-$t$ flow of value $\text{val}(f') - \text{val}(f)$
in the network $G_f$.
\item[2.] Let $G=(V,E)$ be a unit-capacity graph with $n$ nodes and $m$ edges.
Suppose the distance between $s$ and $t$ is at least $d$.
\begin{itemize}
\item Prove that the maximum $s$-$t$ flow in $G$ is at most $m/d$.
\item Suppose $G$ is also a simple graph. Prove that
the maximum $s$-$t$ flow in $G$ is at most $O(n^2/d^2)$ which can provide
a better bound than $m/d$ when $d$ is large. {\em Hint:} Consider
BFS layers from $s$ and prove that there are two adjacent layers with
a total of $O(n/d)$ nodes.
\end{itemize}
\item[3.] Let $G=(V,E)$ be a flow network with integer edge capacities.
We have seen algorithms that compute {\em a} minimum $s$-$t$ cut.
For both problems below assume that you only have black box access to
an algorithm that given $G$ and nodes $s,t$ outputs a minimum cut
between $s$ and $t$.
\begin{itemize}
\item Given $G$ and $s,t$ and an integer $k$
describe an algorithm that checks whether $G$ has
a minimum cut with at most $k$ edges.
\item {\bf Not to submit:} Given $G$ and $s,t$ describe an
algorithm that decides whether $G$ has at least two distinct
minimum $s$-$t$ cuts. Alternatively, does $G$ has a {\em unique}
minimum cut?
\end{itemize}
No proof of correctness necessary but we recommend a brief
justifaction. And make sure you have a clear and
understandable algorithm.
\end{enumerate}
\newpage
{\bf The remaining problems are for self study. Do \emph{NOT} submit for grading.}
\begin{itemize}
\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 Problem 7.13 in KT book asks you to figure out how to reduce node-capacitated flows to edge-capacitated flows.
\item Problem 7.11 in KT asks you an interesting question on whether the
simple greedy algorithm that does not use the residual graph can achieve a decent approximation. It cannot but figuring out the counter example is
quite useful.
\item Problem 7.14, the ``evacuation'' problem.
\item Suppose $G$ is bipartite {\em regular} graph. That is, all vertices
have the same degree $r$. Prove that $G$ has a perfect matching. Prove
that this is not necessarily true in a non-bipartite graph.
\end{itemize}
\end{document}