\bigskip
\handout{Homework 9,  Due Friday, March 13, 2020}
\bigskip

\bigskip



\problem{1 (10 points)} (Page 324, Exercise 13.)
The problem of searching for cycles in graphs arises naturally in financial
trading applications. Consider a firm that trades shares in $n$ different
companies. For each pair $i \ne j$, they maintain a trade ratio $r_{ij}$, meaning
that one share of $i$ trades for $r_{ij}$ shares of $j$. Here we allow the rate $r$ to be
fractional; that is, $r_{ij} = \frac{2}{3}$ means that you can trade three shares of $i$ to get
two shares of $j$.
\medskip

A {\it  trading cycle} for a sequence of shares $i_1, i_2, \ldots, i_k$ consists of
successively trading shares in company $i_1$ for shares in company $i_2$, then
shares in company $i_2$ for shares $i_3$, and so on, finally trading shares in $i_k$
back to shares in company $i_1$. After such a sequence of trades, one ends up
with shares in the same company $i_1$ that one starts with. Trading around a
cycle is usually a bad idea, as you tend to end up with fewer shares than
you started with. But occasionally, for short periods of time, there are
opportunities to increase shares. We will call such a cycle an {\it opportunity}
cycle, if trading along the cycle increases the number of shares. This
happens exactly if the product of the ratios along the cycle is above 1. In
analyzing the state of the market, a firm engaged in trading would like
to know if there are any opportunity cycles.

\medskip

Give a polynomial-time algorithm that finds such an opportunity
cycle, if one exists.

 
\problem{2 (10 points)} Give an algorithm, which given a directed graph $G=(V,E)$, with vertices $s, t \in V$ and an integer $k$, determines the number of paths from $s$ to $t$ of length $k$.  Your algorithm should be polynomial in $k$, $|V|$ and $|E|$.

\problem{3 (10 points)}
Decide whether you think the following statement is true or false.  If it is true, give a short explanation.  If it is false, give a counterexample.

\medskip
{\it
Let $G$ be an arbitrary flow network, with a source $s$, a sink $t$ and a positive integer capacity $c_e$ on every edge $e$; and let $(A,B)$ be a minimum $s-t$ cut with respect to these capacities $\{c_e:e\in E\}$.  Now suppose we add 1 to every capacity; then $(A,B)$ is still a minimum $s-t$ cut with respect to these new capacities $\{1+c_e:e\in E\}$.
}


\problem{4 (10 points)}
In a standard $s-t$ Maximum-Flow Problem, we assume edges have capacities, and there is no limit on how much flow is allowed to pass through a node.  In this problem, we consider the variant of the Maximum-Flow problem with node capacities.

\medskip

Let $G=(V,E)$ be a directed graph, with source $s\in V$, sink $t\in V$, and nonnegative node capacities $\{c_v\ge 0\}$ for each $v\in V$.  Given a flow $f$ in this graph, the flow through a node $v$ is defined as $f^{\mbox{in}}(v)$, the sum of the flows on the incoming edges to $v$.  We say that a flow is feasible if it satisfies the usual flow-conservation constraints and the node-capacity constraints: $f^{\mbox{in}}(v) \le c_v$ for all nodes.

\medskip

Give a polynomial-time algorithm to find an $s-t$ maximum flow in such a node-capacitated network.  Justify the correctness of your algorithm.



\problem{5 (10 points)}

Consider the following flow graph.  Find a maximum flow.  

\def\bb{\makebox(0,0){$\bullet$}}
\setlength{\unitlength}{0.4in}
\begin{center}
\begin{picture}(10,11)
\multiput(0,10)(0,-2){5}%
{\multiput(0,0)(2,0){5}{\bb\vector(0,-1){1.95}\vector(1,0){1.95}}\put(10,0){\bb}}
\multiput(0,10)(2,0){5}{\bb\vector(1,0){1.95}}
\multiput(10,10)(0,-2){5}{\vector(0,-1){1.95}}
\multiput(0,0)(2,0){5}{\bb\vector(1,0){1.95}}
\put(10,0){\bb}
\multiput(0.2,9)(2,2){1}{\makebox(0,0){20}}
\multiput(1,10.2)(2,2){1}{\makebox(0,0){20}}
\multiput(0.2,7)(2,2){2}{\makebox(0,0){10}}
\multiput(1,8.2)(2,2){2}{\makebox(0,0){10}}
\multiput(0.2,5)(2,2){3}{\makebox(0,0){6}}
\multiput(1,6.2)(2,2){3}{\makebox(0,0){6}}
\multiput(0.2,3)(2,2){4}{\makebox(0,0){4}}
\multiput(1,4.2)(2,2){4}{\makebox(0,0){4}}
\multiput(0.2,1)(2,2){5}{\makebox(0,0){3}}
\multiput(1,2.2)(2,2){5}{\makebox(0,0){3}}
\multiput(1,0.2)(2,2){5}{\makebox(0,0){4}}
\multiput(2.3,1)(2,2){5}{\makebox(0,0){4}}
\multiput(3,0.2)(2,2){4}{\makebox(0,0){5}}
\multiput(4.2,1)(2,2){4}{\makebox(0,0){5}}
\multiput(5,0.2)(2,2){3}{\makebox(0,0){7}}
\multiput(6.2,1)(2,2){3}{\makebox(0,0){7}}
\multiput(7,0.2)(2,2){2}{\makebox(0,0){10}}
\multiput(8.2,1)(2,2){2}{\makebox(0,0){10}}
\multiput(9,0.2)(2,2){1}{\makebox(0,0){20}}
\multiput(10.2,1)(2,2){1}{\makebox(0,0){20}}
\put(-0.2,10){\makebox(0,0){{\it s}}}
\put(10.2,0){\makebox(0,0){{\it t}}}

\end{picture}
\end{center}

\begin{itemize}

\item[a)] What is the value of the maximum flow?  Indicate the value of flow on each edge.


\item[b)] Prove that your flow is maximum.

\end{itemize}

\problem{6 (10 Points)}  (Kleinberg-Tardos,  Based on exercise 9,  Page 419)
Network flow issues come up in dealing with natural disasters and other
crises, since major unexpected events often require the movement and
evacuation of large numbers of people in a short amount of time.

\smallskip

Consider the following scenario. Due to a virus outbreak in a region, paramedics have identified a set of $n$ infected people distributed
across the region who need to be rushed to hospitals. There are $k$ hospitals in the region, and each of the $n$ people needs to be brought to a
hospital that is within a half-hour’s driving time of their current location
(so different people will have different options for hospitals, depending
on where they are right now).

\smallskip
At the same time, one does not want to overload any one of the
hospitals by sending too many patients its way. The paramedics are in
touch by cell phone, and they want to collectively work out whether they
can choose a hospital for each of the sick people in such a way that
the load on the hospitals is balanced: Each hospital 
receives at most $\ceiling {n/k}$ 
people.

\smallskip
Give a polynomial-time algorithm that takes the given information
about the people’s locations and determines whether this is possible.