\documentstyle{article}

\setlength{\topmargin}{-0.8in}
\setlength{\oddsidemargin}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.25in}
\pagestyle{empty}

\begin{document}

\noindent
{\large Design and Analysis of Algorithms \hfill Neal Young}

\noindent
{\large Computer Science 45 \hfill}

\noindent
{\large \hfill}

\vspace{.3in}
\begin{center}
{\LARGE Problem Set 2}

Due Friday, April 18.
\end{center}
\vspace{.2in}

  

\begin{enumerate}

\item (Warm-up, don't hand in.)
  Exercise 27.4-2 (Generic Preflow-Push Max.~Flow Algorithm, p.~614).

\item Potential function analysis of the Edmonds-Karp algorithm.

  At any point during the execution of the Edmonds-Karp algorithm:
  \begin{itemize}
  \item Define the {\em shortest path in-degree} of a vertex $v$ to be
    the number of edges coming in to $v$ that are on shortest paths
    from the source to $v$ in the residual graph.

    Let $\mathop{deg}_{sp}(v)$ denote $v$'s shortest-path in-degree.

  \item Let $\mathop{level}(v)$ denote the distance of $v$ from the source
    in the residual graph.

  \item Define potential function $\Phi$ to be
    $\sum_v \mathop{level}(v)|E| - \mathop{deg}_{sp}(v)$.

  \end{itemize}

  (a) Show that this potential function increases with every round of
  the Edmonds-Karp algorithm.  Conclude that the number of rounds 
  is $O(V^2 E)$.

  (b) Modify the potential function to improve the bound to $O(V E)$.

\item  Show that the generic Preflow-Push Algorithm can in fact perform:

(a) $\Omega(V^2)$ lift operations and $\Omega(V^2)$ saturating pushes

(b) (Extra Credit) $\Omega(V^3)$ nonsaturating pushes.

\item
  For the maximum-flow problem, the input is a directed graph
  $G=(V,E)$, a source vertex $s$ and a sink vertex $t$,
  and, for each edge $e\in E$, a capacity $c(e) > 0$.

  For the {\em minimum-cost flow problem}, one is also given
  a {\em cost} $w(e)\ge 0$ for each edge $e\in E$.
  The {\em cost} of a flow $f$ on $G$ is defined to be
  \[\sum_{e : f(e) > 0} f(e)w(e).\]
  The goal is to find a maximum flow that is of minimum cost among all maximum
  flows. 
  
  In the residual graph $G_f=(V,E_f)$
  (as defined in the book for the maximum-flow problem),
  define the {\em cost} $w_f(u,v)$ of each edge $(u,v)\in E_f$
  to be $-w(v,u)$ if $f(v,u)>0$, or $w(u,v)$ otherwise.

  (a) Prove that if the residual graph $G_f$ for a flow $f$
  contains no negative cost cycle (with respect to the cost function $w_f$)
  then $f$ is a minimum-cost flow among flows of value $|f|$.

  (b) Among all $s\leadsto t$ paths in the residual graph, let $p$
  be a shortest path, with respect to the cost function $w_f$.
  Prove that augmenting the flow $f$ by sending flow along $p$
  yields a flow $f'$ that is of minimum-cost among all flows of value $|f'|$.
  
  (c) Why does this imply that in a network with integer capacities,
  there is always an integer minimum-cost maximum flow?
  
\end{enumerate}
\end{document}
