\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{/home/rraj/Courses/3390/S99/macros/localmacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\newcommand{\E}{{\cal E}}
\newcommand{\I}{{\cal I}}

\head{3390}{Analysis of Algorithms}{Spring 1999}{June 4 1999}{26}

\begin{center}
\Large{\bf Sample Solution to Problem Set 3}
\end{center}

\bigskip

{\bf 1. (10 points total)} Consider a version of the activity selection
problem, in which each activity has a {\em weight}, in addition to the start
and finish times.  (For example, the weight may signify the importance of the
activity.)  The goal is to select a maximum-weight set of mutually compatible
activities, where the weight of a set of activities is the sum of the weights
of the activities in the set.
\begin{Itemize}
\item[{\bf (a) (2 points)}]
Give a counterexample to show that the greedy choice made for the activity
selection problem will not work for the weighted activity selection problem.

{\bf Answer:} Consider two activities, the first with start time $1$,
finish time $3$ and weight $1$, and the second with start time $2$, finish
time $4$, and weight $2$.  The greedy algorithm studied in class will yield
the first activity as the solution, while the optimal solution is the second
activity since it has a larger weight than the first one.

\item[{\bf (b) (8 points)}]
Use dynamic programming to solve the weighted activity selection problem.
Analyze the running time of your algorithm.

{\bf Answer:} We first sort all the activities according to their finish
times.  If two activities have the same finish times, we break ties
arbitrarily.  Let the sorted set of activites be $S$ and the activities in $S$
be numbered $1$ through $n$ in the sorted order.  Thus, if $i > j$, we have
$f_i \ge f_j$.

For any $i$ in $1$ through $n$, we now give a recurrence relation for $S[i]$,
a maximum-weight set of mutually compatible activities with $i$ as the last
activity to finish.  
\[
S[i]  =  \max\left\{\{i\}, \max\{S[j] \cup \{i\} : j < i \mbox{ and } i \mbox{ is
compatible with } j\}\right\},
\]
where the maximum is taken over the total weight of the sets.  (Note the
similarity to Problem~3.)

We prove the correctness of the above recurrence relation by induction on $i$.
For $i$ equal to $1$, the proof is trivial.  Consider $i > 1$.  Let $S^*$ be
any set of mutually compatible activities with $i$ as the last activity to
finish.  Let $j$ be the activity with the largest finish time in $S^*
\setminus \{i\}$.  (If no such $j$ exists, then $S^* = \{i\}$ and has weight
at most the weight of $S[i]$ since $S[i]$ includes $i$.) Since $i$ is the last
activity to finish in $S^*$, we have $j < i$.  Therefore, by the induction
hypothesis, the weight of $S^* \setminus \{i\}$ is at most the weight of
$S[j]$.  Since $j$ is compatible with $i$, the recurrence relation guarantees
that the weight of $S[i]$ is at least the weight of $S[j]$ plus the weight of
$i$, which is at least the weight of $S^*$.  Therefore, $S[i]$ is a
maximum-weight set of mutually compatible activities with $i$ as the last
activity to finish.

So the algorithm computes $S[i]$ for all $i$ going from $1$ to $n$.  We then
return the maximum-weight set among these $n$ sets.  The running time of the
algorithm is $O(n^2)$ since the calculation of $S[i]$ takes $O(i)$ time ($i$
compatibility checks and then finding the maximum over a set of $i$ elements).

\end{Itemize}

{\bf 2. (10 points)} Exercise~17.2--4.

{\bf Answer:} Let the gas stations on the trip be numbered $1$ through $m$.
Let the starting point be numbered $0$.  between point $i$ and point $j$.

{\sl Optimal substructure property:} We first consider the subproblems of the
overall problem.  For any point $i$, let $S_i$ denote an optimal sequence of
stops assuming Professor Midas starts from point $i$.  Let $j > i$ be the
first stop in this sequence.  Let $S$ denote the subsequence of $S_i$ that
follows $j$.  Then, we can see that $S$ should be an optimal stopping sequence
assuming Professor Midas starts from point $j$.  Why?  Because, if $S'$ were
another stopping sequence with fewer stops starting from $j$, then $S'_i = j ;
S'$ is a stopping sequence starting from $i$ that has fewer stops than $S_i$,
thus contradicting the assumption that $S_i$ is optimal.  Thus, we have shown
the optimal substructure property.

The optimal substructure property suggests the use of dynamic programming or
greedy algorithms.  Here, we show that Professor Midas can employ a simply
greedy algorithm.  Let $i$ denote the point at which Professor Midas has
stopped at any time.  Initially $i$ equals $0$.  Resuming the trip from $i$,
Professor Midas should make the next stop at the largest $j$ such that the
distance between $i$ and $j$ is at most $n$ miles; that is, greedily cover as
much of the distance as the full tank allows.  If no such $j$ exists, then the
next stop will be the destination point $m$.

{\sl Greedy choice property:} We now prove the correctness of the algorithm.
All we need to do is to establish the greedy choice property.  We will
show that for any $i$, there exists an optimal sequence of stops starting from
$i$ in which the first stop is the same as Professor Midas's choice.  That is,
there is an optimal solution that contains Professor Midas's greedy choice.

Starting from $i$, let $j$ be the next stop made by Professor Midas.  Let
$S_i$ denote an optimal sequence of stops starting from $i$.  If $j$ is the
first stop in $S_i$, then there is nothing to prove.  Otherwise, let $j'$ be
the first stop in $S_i$.  By Professor Midas's greedy choice, it is easy to
see that $j' < j$.  This is because Professor Midas picked the farthest point
allowed by a full tank.  Now suppose we replace the stop $j'$ (and any other
stop $< j$) in sequence $S_i$ by stop $j$.  We first note that this is a valid
sequence of stops.  Second, the number of stops has not increased.  Therefore,
this alternative sequence is also optimal.  We have thus proved that there is
an optimal sequence starting from $i$ that contains $j$ as its first stop.

The greedy choice property and the optimal substructure property prove that
the greedy algorithm is optimal.

{\bf 3. (5 points)} Exercise~24.1--1.

{\bf Answer:} There are two easy ways to prove this claim.  The first is using
a cut and paste argument.  Let $e$ be any minimum-weight edge.  Let $T$ be any
MST.  If $e$ belongs to $T$, then there is nothing to prove.  Otherwise, if we
add $e$ to $T$, we get a cycle.  Let $e' \neq e$ be any other edge in the
cycle.  Then, clearly $T - e' + e$ is a spanning tree.  Since $w(e') \ge
w(e)$, $T - e' + e$ is an MST.

The second proof is using the correctness of Kruskal's algorithm.  In this
algorithm, the first step is to sort all the edges according to their weight
in nondecreasing order.  In this sorted order, any minimum-weight edge $e$ can
be placed in first place.  Since Kruskal's algorithm includes the first edge
into the MST, it follows that $e$ is in some MST.

{\bf 4. (10 points)} Let $T$ be any minimum spanning tree of $G$.  Let $T'$ be
a spanning tree of $G$, not necessarily a minimum spanning tree.  Prove or
disprove the following statement: The largest edge weight of $T$ is at most
the largest edge weight of $T'$.

{\bf Answer:} Let $e$ be a maximum-weight edge in $T$.  We now show that there
is at least one edge in $T'$ that has weight at least $w(e)$.  It then follows
that the largest edge weight of $T$ is at most the largest edge weight among
all spanning trees.

The edge $e$ partitions $T$ into two subsets of vertices, say $S$ and $V - S$.
Since $T'$ is a spanning tree of $G$, there is an edge $e'$ in $T$ that
crosses the cut $(S, V - S)$.  We now show that $w(e) \le w(e')$.  The proof
is by contradiction.  If $w(e) > w(e')$, then $T'' = T - e + e'$ is a spanning
of lesser weight than $T$, contradicting the fact that $T$ is an MST.
Thus $w(e) \le w(e')$, hence completing the proof.


{\bf 5. (15 points)} One can model a communication network by a weighted
directed graph $G$, in which the vertices of $G$ represent the nodes of the
network, the edges of $G$ represent the communication links of the network and
the weight of an edge is the bandwidth of the link.  We define the {\em
effective bandwidth}\/ of a path $p$ as the bandwidth of the minimum-bandwidth
link in $p$.

Design and analyze an efficient algorithm to determine a path with the largest
effective bandwidth from a given node $s$ to a given node $t$.  If no path
from $s$ to $t$ exists, then your algorithm must indicate so.  Justify the
correctness of your algorithm.  (Assume that the bandwidth of every link is
positive.)

{\bf Answer:} We can modify Dijkstra's algorithm by mainly replacing the the
``$\min$'' operation by ``$\max$'', the ``$+$'' operation by ``$\min$'', and
the ``$>$'' operation by ``$<$''.  These entail three kinds of changes in the
algorithm.  

First, consider the initialization routine {\sc
Initialize-Single-Source}$(G,s)$, defined on page~520 of text.  In line~2, we
will set $d[v]$ to $0$ and in line~4, we set $d[s]$ to $\infty$.

Second, the {\sc Relax}$(u,v,w)$ operation will change to the following code.
\begin{tabbing}
{\sc Relax}$(u,v,w)$\\
1. \= \myif\ \= $d[v] < \min\{d[u], w(u,v)\}$\\
2. \>  \> {\bf then} \= $d[v] = \min\{d[u], w(u,v)\}$\\
3. \> \> \> $\pi[v] = u$
\end{tabbing}

Finally, in {\sc Dijkstra}$(G,w,s)$ (page~527), instead of extracting the
vertex with the minimum $d$ value in line~5, we extract the vertex with the
maximum $d$ value.

The proof of Dijkstra's algorithm for shortest paths proceeds by showing two
claims: (a) $d[u] \ge \delta(s,u)$ for all $u$ at all times, and (b) at the
time $u$ is extracted from $Q$, $d[u] = \delta(s,u)$.  For establishing these
two claims, the two main properties that we need are (i) if the last edge on
the shortest path from $s$ to $v$ is $(u,v)$, then $\delta(s,v) = \delta(s,u)
+ w(u,v)$ (Corollary~25.2 on page 519 of text), and (ii) for any edge $(u,
v)$, $\delta(s,v) \le \delta(s,u) + w(u,v)$ (Lemma~25.3, page 520 -- triangle
inequality).

In our present situation, we are seeking the path with the largest effective
bandwidth -- not the shortest path.  Let $\Delta(s,u)$ denote the effective
bandwidth of the path from $s$ to $u$ with the largest effective bandwidth.
Claims (a) and (b) translate to the following two claims: (A) $d[u] \le
\Delta(s,u)$ for all $u$ at all times, and (b) at the time $u$ is extracted
from $Q$, $d[u] = \Delta(s,u)$.  We can establish these two claims by showing
properties (I) and (II) analogous to the properties (i) and (ii) above: (I) if
the last edge on the path with the largest effective bandwidth from $s$ to $v$
is $(u,v)$, then $\Delta(s,v) = \min\{\Delta(s,u), w(u,v)\}$, and (II) for any
edge $(u, v)$, $\Delta(s,v) \ge \min\{\delta(s,u), w(u,v)\}$.  Note that all
we have done is to replace $+$ by $\min$ and $\le$ by $\ge$.  Both claims~(I)
and~(II) can be proved in a manner very similar to the proofs of~(i) and~(ii),
that we went through in class.

One worthwhile remark is that the proof of claim~(i) for the shortest-paths
case can be done by establishing the optimal substructure property -- that is,
subpaths of shortest paths are shortest paths, something that is not always
true for the effective-bandwidth case!  Nevertheless, claim (I) can be proved
by a simple argument based on contradiction.

{\bf 6. (10 + 5 = 15 points)} Problem~25--3.

{\bf Answer:} We view the given information as a weighted directed graph $G$
in which the the currencies form the vertices and there is a directed edge
between any two vertices.  Thus, there are $n$ vertices and $n(n-1)$ edges.

\begin{itemize}
\item[(a)] Once we have specified the graph (without yet specifying the
weights), there are two ways of solving this problem.  One is by transforming
the problem to one of finding the existence of a negative weight cycle in a
graph -- here we will judiciously choose the weights.  And the other is to set
the weight of the edge $(i,j)$ to be the exchange rate $R(i,j)$ and then
modify the Bellman-Ford algorithm to determine whether a cycle with product $>
1$ exists.  In the latter approach, we also need to show that the modification
of the Bellman-Ford algorithm works correctly.

Here we consider the first approach.  For vertices (currencies) $i$ and $j$,
in $G$, we let the weight of edge $(i,j)$ equal $- \lg (R(i,j))$.  We now show
that arbitrage exists if and only of there exists a negative weight cycle in
$G$.  This is easy to see since the weight of a cycle $i_1 \rightarrow i_2
\rightarrow \ldots \rightarrow i_k \rightarrow i_1$ equals 
\[\sum_{1 \le j \le k} - \lg (R(i_j, i_{j+1})) = - \lg\left(\prod_{1 \le j \le k}
R(i_j, i_{j+1})\right),
\] 
thus implying that the weight of the cycle is negative if and only if
$\prod_{1 \le j \le k} R(i_j, i_{j+1})$, which is the condition for arbitrage.

We have thus reduced our problem to that of finding whether there exists a
negative-weight cycle in $G$.  We simply invoke the Bellman-Ford algorithm
starting from any source.  Since every vertex is accessible from every other
vertex, if a -ve weight cycle exists in $G$, we will find its existence using
the algorithm.  The running time of the algorithm is $O(VE) = O(n \cdot n^2) =
O(n^3)$.

\item[(b)] In order to extract the cycle of currencies that yields arbitrage,
we employ $n(n-1) + 1$ iterations of the Bellman-Ford algorithm.  In iteration
$0$, we run the Bellman-Ford algorithm on $G$.  If no negative weight cycle is
found, then there is nothing to do further.  If the existence of a
negative-weight cycle is indicated, then we perform the next $n(n-1)$
iterations (one associated with each of the $n(n-1)$ edges).

We number the edges arbitrarily from $1$ to $n(n-1)$.  We also select a source
$s$ arbitrarily.  In iteration $1$, we run the Bellman-Ford algorithm on the
subgraph of $G$ obtained after removing edge $1$.  If we find no
negative-weight cycle, then this implies that $1$ lies in all negative-weight
cycles or lies along a path from the source that leads to all negative-weight
cycles.  In this case, we keep edge $1$ in all future iterations.  Otherwise,
we remove $1$ from the graph.

So, in general, at the start of iteration $i$, we have a graph $G_{i-1}$ which
is a subgraph of $G$ with a subset of the edges $\{1, 2, \ldots, i-1\}$
removed.  In iteration $i$, we run the Bellman-Ford algorithm on the subgraph
$G'$ of $G_{i-1}$ in which edge $i$ has been removed.  If a negative-weight
cycle exists, then we set $G_i$ to $G'$; otherwise, we set $G_i$ to $G_{i-1}$.

Thus, after iteration $n(n-1)$, we have a subgraph $G_n$ which consists of a
set of edges, each of which belongs to every negative weight cycle in $G_n$ or
lies on a path from $s$ to every negative-weight cycle.  Thus, the graph $G_n$
is simply a (possibly empty) path from source $s$ to a negative-weight cycle.
We can extract the negative-weight cycle from $G_n$ by a search from $s$
(depth-first or breadth-first).

Since there are $O(n^2)$ iterations, each involving a Bellman-Ford algorithm
of $O(n^3)$ running time, the running time of the complete algorithm equals
$O(n^5)$. 
\end{itemize}

{\bf 7. (10 points)}
Exercise 26.1--4.

{\bf Answer:} We will concern ourselves only with the calculation of the
lengths of the shortest paths.  The actual shortest path calculations can be
done as usual.  Let $W$ denote the weight matrix; that is $w_{ij}$ is the
weight of the edge $(i,j)$, if it exists, and $\infty$, otherwise.  We have
seen that $W^{n-1}$ yields the all-pairs shortest path lengths, where the $+$
and $\cdot$ of matrix multiplication is replaced by $\min$ and $+$,
respectively.  

Given any vertex $s$, the $s$th row of the matrix $W^{n-1}$ contains the
lengths of the shortest paths from $s$ to other vertices in the graph.  Let
$e_s$ denote the ``unit'' row vector in we have a $0$ at the $s$th column and
$\infty$ in every other column.  That is, $e_s$ is of the form
\[
\left(\infty, \ldots, \infty, 0, \infty, \ldots, \infty\right).
\]
We now can find the single-source shortest paths lengths with $s$ as the
source by simply ``multiplying'' $e_s$ with $W^{n-1}$.  (Note that in this
multiplication too, we have the same interpretation of $+$ and $\cdot$ as
$\min$ and $+$, respectively.)  Let $D_s$ denote the vector of the
single-source shortest paths lengths with $s$ as the source.  Then, we have:
\[ D_s = e_s \cdot W^{n-1}.\]

The above calculation corresponds to a Bellman-Ford-like algorithm in the
following way.  We calculate a series of vectors $D_s^{(0)} , D_s^{(1)},
\ldots, D_s^{(n - 1)}$.  At any time the vector $D_s$ will be analogous to the
vector $(d[1], d[2], \ldots, d[n])$.  We first set $D_s^{(0)}$ to $e_s$.  This
is analogous to {\sc Initialize-Single-Source}.  The calculation of $D_s^{(i)}
= D_s^{(i-1)} \cdot W$ can be done in the following manner 
\begin{tabbing}
1. \= {\bf for} \= $k = 1$ to $n$\\
2. \>\> $D_s[j] \leftarrow \min_{1 \le k \le n} D_s^{(i-1)}[k] + W_{kj}$
\end{tabbing}

The above pseudocode is analogous to the $i$th iteration of the Bellman-Ford
algorithmin the sense that we relax every edge $(j,k)$ in the graph.  These
relaxations are hidden in line 2 of the above code.  There is a subtle
difference, however, between the $i$th iteration of the Bellman-Ford algorithm
and the above calculation, which makes the two algorithms somewhat different.
In Bellman-Ford, we are always manipulating the same vector $(d[1], d[2],
\ldots, d[n])$.  This implies that a change to $d[j]$ in an iteration may also
be reflected in the calculation of $d[k]$ in the {\em same iteration}\/ (if we
relax edge $(j,k)$ after changing $d[j]$), something that will not happen in
the above pseudocode since we always compute a new vector $D_s^{(i)}$ from
$D_s^{(i-1)}$.  Apart from this subtle difference, the two algorithms are analogous.

{\bf 8. (3 $\times$ 8 = 24 points)} Problem~27--3.

{\bf Answer:} The notation used below is the same as that developed in the
problem.
\begin{itemize}
\item[(a)] We are given a finit-capacity cut $(S,T)$.  We need to show that if
$E_j \in T$, then $I_k \in T$ for each $I_k \in R_j$.  The proof is by
contradiction.  Consider any $E_j$ in $T$ and any $I_k$ in $R_j$.  If $I_k$ is
in $S$, then the edge $(I_k, E_j)$ crosses the cut $(S, T)$.  This edge has infinite
capacity.  Thus, the cut $(S,T)$ has infinite capacity, leading to a
contradiction.

\item[(b)] We need to determine an optimal pair $(\E, \I)$ that yields the
maximum net revenue, where $\E$ is a set of experiments and $\I$ is a set of
instruments which includes all instruments needed for the experiments in $\E$.
We show a one-to-one correspondence between the feasible pairs $(\E,
\I)$ and the finite-capacity cuts $(S,T)$ of $G$.  

Consider any feasible pair $(\E, \I)$.  Let the payment for experiments in $\E$
be denoted by $p(\E)$ and the cost of instruments in $\I$ by $c(\I)$.  Thus
the revenue $r(\E, \I)$ of the pair $(\E, \I)$ equals $p(\E) - c(\I)$.  We now
define a cut $(S, T)$ as follows.  Let $T$ equal the set $\{t\} \cup \E \cup
\I$, and $S$ equal the complement of $T$.  The capacity of the cut is:
\begin{eqnarray*}
\sum_{u \in S} \sum_{v \in T} c(u,v) & = & \sum_{I \in \I} c(s,I) + \sum_{E \in
E - \E} c(E,t)\\
& = & c(\I) + p(E) - p(\E)\\
& = & p(E) - r(\E, \I).
\end{eqnarray*}
For each feasible solution $(\E, \I)$ to the NASA problem, we have thus
defined a cut $(S, T)$ such that $c(S,T) = p(E) - r(\E, \I)$.  (Note that
$p(E)$ is the sum of the payments of all the experiments.)   

Similarly, for each finite-capacity cut $(S, T)$, we can construct a feasible
solution $(\E, \I)$ such that $c(S, T) = p(E) - r(\E, \I)$.  It thus follows
that the maximum net revenue equals the difference between $p(E)$ and the
capacity of the minimum cut.

\item[(c)]
By part~(b), the NASA problem reduces to finding the minimum capacity cut of
$G$.  We can do that by finding the maximum flow using the Edmonds-Karp
algorithm and then invoking the proof of the max flow min cut theorem (Theorem
27.7 of text).  

The algorithm is as follows.  We first run the Edmonds-Karp max flow
algorithm.  Let $f$ be the maximum flow and $G_f$ denote the residual network
obtained at the end.  By the proof of Theorem~27.7, we know that if we let $S$
be the set of all vertices reachable from $s$ in the residual network, and $T$
be the set of all other vertices, then the cut $(S, T)$ is a minimum capacity
cut.  (Please refer to page 593 of text or your class notes.)  We can thus
determine the minimum capacity cut by a simple depth-first search or
breadth-first search.  The cut then yields the set of experiments to perform.

We now calculate the total running time.  The number of vertices in the graph
is $m + n + 2$.  The total number of edges is $m + n + r$.  The running time
of the Edmonds-Karp algorithm is therefore $O((m + n)(m + n + r)^2)$.  The
running time of the final search is therefore $O(m + n + r)$.  Thus, the total
running time is $O((m + n)(m + n + r)^2)$.
\end{itemize}

{\bf 9. (2 $\times$ 8 = 16 points)} Problem~27--4.

{\bf Answer:} Both the parts can be solved by using the concepts of augmenting
paths and the residual network.
\begin{itemize}
\item[(a)] We first note that the increase in capacity of one edge can
increase the max flow can increase by at most $1$.  This follows directly from
the max-flow min-cut theorem and the fact that the min cut capacity can
increase by at most $1$.  Therefore, either the max flow increases by $1$ or
remains the same.

Consider the residual network obtained from the original maximum flow $f$.
Let $G_f$ denote the residual network.  Suppose we are given that the capacity
of the edge $(u,v)$ has increased by $1$.  We increase the capacity of the
edge $(u,v)$ in the residual network by $1$.  If $(u,v)$ was not in the
residual network, then we now add it and set its residual capacity to $1$.
Let $G'_f$ denote the residual network thus obtained.  We now run one
iteration of the Ford-Fulkerson algorithm on $G'_f$.  If we find an augmenting
path from $s$ to $t$ in $G'_f$, then the flow increases by $1$; otherwise, it
remains the same.

The running time of this algorithm is the same as the running time of one
iteration of the Ford-Fulkerson algorithm, which is $O(V + E)$.  

\item[(b)] We first note that the decrease in capacity of one edge can
decrease the max flow can increase by at most $1$.  This follows directly from
the max-flow min-cut theorem and the fact that the min cut capacity can
decrease by at most $1$.  Therefore, either the max flow decreases by $1$ or
remains the same.

Consider the residual network obtained from the original maximum flow $f$.
Let $G_f$ denote the residual network.  Suppose we are given that the capacity
of the edge $(u,v)$ has decreased by $1$.  We consider two cases.

The first case is when $(u,v)$ is in $G_f$.  This means that the residual
capacity of $(u,v)$ was at least $1$ before the decrease.  In this case,
$(u,v)$ can still carry its original flow even if its capacity is decreased by
$1$.  Therefore, the max flow value remains the same.  To maintain the
residual network, we reduce the residual capacity of $(u,v)$ by $1$; if its
residual capacity becomes $0$, we remove it from the graph.

The second case is when $(u,v)$ is not in $G_f$.  This implies that $f(u,v)$
equals $c(u,v)$.  The capacity of $(u,v)$ has decreased by $1$, however.
Therefore, we have to reduce the flow on $(u,v)$ by $1$.  In order to maintain
the flow conservation law, we have to reduce the flow on each edge along some
path from $s$ to $t$ containing $(u,v)$ by $1$.  We find such a path by
traversing the residual network.  We find a path from $u$ to $s$ and from $t$
to $v$ in the residual network.  This together with the edge $(v,u)$ in the
residual network gives a path $p$ from $t$ to $s$ in the residual network.
For each edge $(x,y)$ in the path $p$, we make the following changes: we
increase $f(x,y)$ by $1$ and decrease $f(y,x)$ by $1$.  Note that one of the
effects of these changes is that $f(u,v)$ decreases by $1$, thus satisfying
the capacity constraint of $(u,v)$.  Furthermore, the net flow value has also
decreased by $1$.  We now consider the new residual network $G'$.  We run one
more iteration of the Ford-Fulkerson algorithm.  If we find an augmenting path
from $s$ to $t$ in $G'$, then the flow increases by $1$, thus resulting in the
same max flow as before; otherwise, it remains the same, thus resulting in an
overall flow that has decreased by $1$.

The above algorithm performs two searches in $G_f$, one from $t$ to $v$ and
the other from $u$ to $s$.  Each of these takes $O(V + E)$ time.  And finally,
we perform one iteration of the Ford-Fulkerson algorithm, which takes $O(V +
E)$ time.  The total running time is thus $O(V + E)$.
\end{itemize}
\end{document}