\documentclass[11pt]{article}
\usepackage{program}


\title{6.046 Problem Set 8}
\author{Chris Laas: Section G}
\date{April 20, 2000}

\pagestyle{myheadings}
\markright{Chris Laas: Section G \hfil 6.046J/18.410J \hfil 4/20/2000}

\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{\arabic{enumii}.}
\NumberProgramstrue
\def\RETURN{\keyword{return}\ }
\def\MOD{\mbox{mod}\ }
\def\text#1{\mbox{ #1 }}
\def\AND{\mbox{\bf\ and }}
\def\OR{\mbox{\bf\ or }}
\def\TRUE{\mbox{\bf true}}
\def\FALSE{\mbox{\bf false}}
\def\choice#1{\left\{ \begin{array}{ll} #1 \end{array} \right.}
\def\({\left(}
\def\){\right)}
\def\[{\left[}
\def\]{\right]}



\begin{document}
\maketitle






\section*{Problem 8-1}
\begin{enumerate}

\item%(a)

This algorithm is not correct.  As a counterexample, take the
isosceles right triangle consisting of the points $A(0,-1)$, $B(0,1)$,
and $C(1,0)$.  As noted, we can rotate the axes slightly so that $A$
and $B$ do not have the same x-coordinate, so let's say that we're
really working with the triangle $A'(-\epsilon,-1)$, $B'(\epsilon,1)$,
$C'(1,-\epsilon)$ for $0 < \epsilon \ll 1$.  Clearly, $A'B'C'$ has the
same minimum spanning tree as $ABC$: the MST contains both legs $AC$,
$BC$, but not the hypotenuse $AB$, since the hypotenuse is the longest
side.  However, if we perform this algorithm on $A'B'C'$, the
hypotenuse is the first edge added, since the algorithm always
connects $p_1$ and $p_2$, and in this run, $p_1 = A'$ and $p_2 = B'$.
Thus, this algorithm does not construct the MST on $A'B'C'$.


\item%(b)

This algorithm is not correct.  We can take the same isosceles right
triangle $ABC$ (where the points are $A(0,-1)$, $B(0,1)$, and
$C(1,0)$) as a counterexample.  For, let's say that the algorithm
draws its first dividing line between $C$ and the other points, and
the second dividing line between $A$ and $B$.  Then the tree it
constructs will include the hypotenuse $AB$ as an edge, which rules
the tree out as a minimal spanning tree.


\item%(c)

This algorithm is correct.  The invariant held by this algorithm is
that the current spanning forest is a minimal spanning forest of the
edges considered so far.  (A spanning forest of a graph $G$ is a
subgraph whose connected components are spanning trees of $G$'s
connected components.)  In the base case, this is trivially true,
since the forest consisting of all nodes and no edges is the only
forest when there are no edges.

Let us assume that the invariant holds true at the beginning of an
iteration of the algorithm: $F$ is a minimal spanning forest of the
subgraph $G$ which consists of the edges considered so far.  We must
prove that it remains true after we consider an additional edge $e$,
which, because the edges are sorted by length, will be shorter than
any edge currently in the graph.  In other words, we must prove that
the graph $F'$ generated by an iteration of the algorithm is a minimal
spanning forest of the subgraph $G' = G \union \{ e \}$.

In the case that the edge $e$ connects two distinct trees, $e$ must be
in {\em any} spanning forest of the new graph $G'$.  This is because,
if it were not, then the component of $G'$ containing $e$ would not be
spanned by any component of the forest $F'$.  Thus, trivially, $e$ is
in any minimal spanning forest $F'$ of the new graph.

In the case that the edge $e$ connects two vertices $x$, $y$ in the
same tree $T$ of the forest $F$, the algorithm constructs $F'$ by
adding $e$ to $F$ while removing the longest edge $f$ on the path
between $x$ and $y$ in $T$.  Let's assume (for purposes of
contradiction) that $F'$ is not a minimal spanning forest for $G'$:
then there is a minimal spanning forest $F''$ of $G'$ with less total
length than $F'$.  Since $F$ was a minimal spanning forest for $G$ and
$G$ has only changed in the component containing $x$ and $y$, we see
that the component $T''$ of $F''$ containing $x$ and $y$ has less
total length than the component $T'$ of $F'$ containing $x$ and $y$.
(Also, clearly, since $F''$ is a minimal spanning forest, $T''$ is a
minimal spanning tree for that component of $G'$.)  Now, consider the
case that $e$ is not in $T''$.  Then we could construct yet another
forest by removing the longest edge on the path between $x$ and $y$ in
$F''$ and adding $e$; since $e$ is the shortest edge in $G'$, this new
forest would have less total length than $F''$, contradicting the
construction of $F''$ as a minimal spanning forest.  On the other
hand, consider the case that $e$ is in $T''$.  Then, removing $e$
splits $T''$ into two components, which can be rejoined by adding one
edge $f'$ which was on the path from $x$ to $y$ in $T$, giving another
spanning tree for this component of $G$.  However, this spanning tree
must have shorter total length than $T$, since by construction the
length of $f$ is greater than or equal to the length of $f'$, and the
total length of $T''$ is less than the total length of $T'$.  This,
however, is a contradiction, since $T$ is by construction a minimal
spanning tree of this component of $G$.

Thus, in conclusion, the current spanning forest is always a minimal
spanning forest of the edges considered so far.  This, combined with
the postcondition that, at the end, we have considered all edges,
means that the final spanning forest is a minimal spanning tree, since
it is a minimal spanning forest and is also a spanning tree (since,
after we have considered all edges, $G$ consists of a single
component).

\end{enumerate}
\newpage






\section*{Problem 8-2}
\begin{enumerate}

\item%(a)

If a graph $G = (V,E)$ can be 2-colored, then there exists a function
$\chi: V \to \{1,2\}$ such that for every edge $(u,v) \in E$, we have
$\chi(u) \neq \chi(v)$.  Then, if we let $A$ be the set of nodes $u$
such that $\chi(u) = 1$ and $B$ be the set of nodes $u$ such that
$\chi(u) = 2$, we have partitioned $G$ into a bipartite graph: for, if
we take any edge $(u,v) \in E$, then $\chi(u) \neq \chi(v)$, and thus
one of $u$ and $v$ is in $A$, and the other is in $B$.  Thus all edges
go between $A$ and $B$.

Conversely, if $G = (V,E)$ is bitartite, then the nodes can be
partitioned into two subsets $A$ and $B$ in such a way that all edges
go between $A$ and $B$.  Thus, we can define $\chi: V \to \{1,2\}$ by

$$\chi(u) = \choice{1 & \IF u \in A \\ 2 & \IF u \in B}$$

Then, for any edge $(u,v) \in E$, $\chi(u) \neq \chi(v)$, since one of
$u$ and $v$ is in $A$ and the other is in $B$.  Thus, $\chi$ is a
2-coloring of $G$.


\item%(b)

This algorithm attempts to generate a 2-coloring of the graph by
performing a breadth-first-search and alternating colors as it goes.
All nodes start out gray; then, when they are discovered, they are
colored so as not to have the same color as any adjacent nodes.  If
this is not possible, $|nil|$ is returned to signify that the graph is
not bipartite.

\begin{program}
|Bipartite-Partition|(G)
\quad\tab \FOR \mbox{every vertex\ } u \in V[G]
              |color|[u] \gets |Gray|
              |confirmed|[u] \gets \FALSE
              \untab%
          \FOR \mbox{every vertex\ } u \in V[G]
              \IF |color|[u] = |Gray|
                 \THEN |color|[u] \gets |White|
                       \IF |Bipartite-Partition-BFS|(u) = \FALSE
                          \THEN \FOR \mbox{each white or black unconfirmed vertex\ } v \in V[G]
                                     |color|[v] \gets |Gray|
                                |color|[u] \gets Black
                                \IF |Bipartite-Partition-BFS|(u) = \FALSE
                                   \THEN \RETURN |nil|
                                         \untab%
                                   \untab%
                                \untab%
                          \untab%
                       \FOR \mbox{each white or black unconfirmed vertex\ } v \in V[G]
                           |confirmed|[v] = \TRUE
                       \untab%
                 \untab%
              \untab%
          A \gets \emptyset
          B \gets \emptyset
          \FOR \mbox{every vertex\ } u \in V[G]
              \IF |color|[u] = |White|
                 \THEN A \gets A \union \{ u \}
                 \ELSE B \gets B \union \{ u \}
                       \untab%
                 \untab%
              \untab%
          \RETURN (A,B)
\end{program}

\vbox{
\begin{program}
|Bipartite-Partition-BFS|(s)
\quad\tab Q \gets \{ s \}
          \WHILE Q \neq \emptyset
                 u \gets |Dequeue|(Q)
                 \FOR \mbox{each\ } v \in |Adj|[u]
                     \IF |color|[v] = |color|[u]
                        \THEN \RETURN \FALSE
                              \untab%
                        \untab%
                     \IF |color|[v] = |Gray|
                        \THEN \IF |color|[u] = |White|
                                 \THEN |color|[v] \gets |Black|
                                 \ELSE |color|[v] \gets |White|
                                       \untab%
                                 \untab%
                              |Enqueue|(Q, v)
                              \untab%
                        \untab%
                     \untab%
                 \untab%
          \RETURN \TRUE
\end{program}
}

First, to get the issue of termination out of the way:
$|Bipartite-Partition-BFS|$ must terminate, because only gray nodes
are ever enqueued, and nodes are always colored white or black before
being enqueued.  Thus, since all other loops are over data structures
of finite size, $|Bipartite-Partition|$ terminates.

The first loop of $|Bipartite-Partition|$ merely sets up all nodes to
be gray, or undiscovered.  The second loop is the main algorithm:  it
constructs a 2-coloring of the graph if possible, or returns nil if
not possible.  The third and final loop is simple to understand:  it
constructs the partitioning sets $A$ and $B$ from the 2-coloring.  The
remainder of the correctness proof will deal with proving the
construction of the 2-coloring correct.

First, let us assume that the algorithm does not return nil; we must
show that the coloring of the nodes is a 2-coloring.  We know that, by
the end of the main loop, all nodes are either black or white, since
any gray nodes will have been colored by $|Bipartite-Partition-BFS|$.
Assume that the white-black coloring is not a 2-coloring.  Then there
exists an edge $(u,v)$ such that $|color|[u] = |color|[v]$.  During
the BFS, edge $(u,v)$ had been considered at one point, when
inspecting $|Adj|[u]$.  At that point, it was known that $u$ was not
gray; if $v$ was gray, then it was explicitly given a color which was
opposite to $u$'s.  If $v$ was not gray, then its color was checked
against $u$'s, and if they were equal, then $|Bipartite-Partition|$
would have returned nil, which contradicts the assumption.  Thus, we
can conclude that $|color|[u] \neq |color|[v]$ for any edge $(u,v)$,
and hence, the algorithm has generated a 2-coloring of the graph.

On the other hand, let us assume that the algorithm returns nil.  Then
there exists an edge $(u,v)$ such that $|color|[u] = |color|[v]$ and
neither color is gray.  Since the 2-coloring of each node reachable
from a source is uniquely determined by the color of the source, and
we try both possibilities, there exists no 2-coloring of the graph.

This algorithm considers each edge a maximum of two times; once with
the source White, and once with it black.  Thus, the run time of the
algorithm is $O(V + E)$.

\end{enumerate}
\newpage







\section*{Problem 8-3}

This problem is trivial.  The algorithm is as follows:

\renewcommand{\labelenumi}{\arabic{enumi}.}
\begin{enumerate}

\item
Construct the negative weight function $w'(u) = -w(u)$.

\item
Perform the topological-sorting-based $|DAG-Shortest-Paths|$ algorithm,
using $w'$ as the weight function.

\item
Construct the array $D$ by taking the negatives of each of the path
lengths computed by $|DAG-Shortest-Paths|$.

\end{enumerate}
\renewcommand{\labelenumi}{(\alph{enumi})}

The algorithm terminates because each of its steps terminates; it is
correct because any path of minimal weight using $w'$ will have
maximal weight using $w$, and because $|DAG-Shortest-Paths|$ works on
graphs with negative-weight edges.

Because steps 1 and 3 run in $\Theta(V)$ time and step 2 runs in
$\Theta(V+E)$ time, this algorithm runs in $\Theta(V+E)$ time.


\newpage







\section*{Problem 8-4}

This algorithm works by first constructing the all-pairs shortest
paths in the graph, and then finding the shortest total path from a
node to another node and back, i.e. the shortest cycle.  I assume that
$W[G]$ is the edge-weight matrix of the graph $G$; if $G$ is specified
in a form other than an edge-weight matrix, $W[G]$ could be easily
computed from $G$ in $O(n^2)$ time.  As a subroutine, I use the
Floyd-Warshall all-pairs shortest-paths algorithm, which returns a
distance matrix $D$ and a predecessor matrix $\Pi$.

\begin{program}
|Minimum-Weight-Cycle|(G)
\quad\tab (D, \Pi) \gets |Floyd-Warshall|(W[G])
          m \gets \infty				\label{8.4:A}
          \FOR i \gets 2 \rdots n
              \FOR j \gets 1 \rdots i-1
                  \IF d_{ij} + d_{ji} < m
                     \THEN m \gets d_{ij} + d_{ji}
                           a \gets i
                           b \gets j			\label{8.4:B}
                           \untab%
                     \untab%
                  \untab%
              \untab%
          \FOR i \gets 1 \rdots n			\label{8.4:C}
              \IF (u_i,u_i) \in E[G] \AND w(u_i,u_i) < m
                 \THEN m \gets w(u_i,u_i)
                       a \gets i
                       b \gets i			\label{8.4:D}
                       \untab%
                 \untab%
              \untab%
          \IF m = \infty
             \THEN |Print|(\mbox{``there is no cycle in the graph''})
             \ELSE |Print|(\mbox{``minimum cycle weight:''\ } m)
                   \IF a = b
                      \THEN |Print|(a)
                      \ELSE |Print-All-Pairs-Shortest-Path|(\Pi, a, \pi_{ab})
                            |Print-All-Pairs-Shortest-Path|(\Pi, b, \pi_{ba})
\end{program}

The first line computes all-pairs shortest paths, taking $\Theta(n^3)$
time.  The second segment, lines \ref{8.4:A}-\ref{8.4:B}, is the
primary body of the algorithm: it considers every pair of vertices in
turn, and finds the minimum-weight cycle with at least two vertices.
The second segment takes $\Theta(n^2)$ time, as can be seen from its
nested loop structure.  The third segment, lines
\ref{8.4:C}-\ref{8.4:D}, is a little wart on the algorithm that is
necessary because Floyd-Warshall and the second segment do not
consider one-vertex one-edge cycles; it determines whether any vertex
constitutes a one-vertex cycle with less weight than the
minimum-weight two-or-more-vertex cycle.  The third segment only takes
$\Theta(n)$ time, since it need only consider one edge per vertex.
The final segment prints the results:  if the minimum cycle weight $m$
is infinity, there is no cycle the graph; else, the minimum-weight
cycle's vertices are printed in order.  The final segment has no loop,
and hence takes $\Theta(1)$ time.

Clearly, the Floyd-Warshall run time dominates the run time of the
algorithm as a whole; hence, this algorithm runs in $\Theta(n^3)$
time.



\newpage







\section*{Problem 8-5}
\begin{enumerate}

\item%(a)

This problem is exactly equivalent to the problem of finding
negative-weight cycles in a weighted directed graph.  For, let
the vertices of a completely connected graph $G$ be
$V = \{ 1, 2, \dots, n \}$, and let the edge weights be defined by the
function $w(i,j) = -\log R[i,j]$.  (We assume that $R[i,j \neq 0]$ for
any $i$ and $j$, i.e. you can buy some amount of currency $i$ with
currency $j$.  If this is not the case, the analogy can still be
made to work by substituting $w(i,j) = \infty$ if $R[i,j] = 0$, or by
eliminating those edges.)  We can easily see that there exists
a sequence of currencies
$\langle c_{i_1}, c_{i_2}, \dots, c_{i_k} \rangle$
such that
$$ R[i_1,i_2] \cdot R[i_2,i_3] \cdots R[i_{k-1},i_k] \cdot R[i_k,i_1] > 1 $$
if and only if there exists a cycle $\langle i_1, i_2, \dots, i_k \rangle$
in the graph such that
$$ w(i_1,i_2) + w(i_2,i_3) + \cdots + w(i_{k-1},i_k) + w(i_k,i_1) < 0 $$
i.e.,
$$ - \log R[i_1,i_2] - \log R[i_2,i_3] - \cdots
   - \log R[i_{k-1},i_k] - \log R[i_k,i_1] < 0 $$

Hence, this first problem of simply {\em detecting} potential
arbitrage sequences reduces to the problem of detecting
negative-weight cycles in a completely connected weighted directed
graph.  We already know we can do this with the Bellman-Ford
algorithm; hence, an algorithm to detect arbitrage sequences is:

\begin{enumerate}
\item
Construct the graph and weight function $w$ as shown above.  This
takes $O(n^2)$ time.
\item
Pick any node $i$ and perform $|Bellman-Ford|(G, w, i)$:  if
$|Bellman-Ford|$ detects a negative-weight cycle, there exists an
arbitrage sequence of currencies.  This takes $O(VE) = O(n^3)$ time.
\end{enumerate}

Thus, the total running time of the algorithm is $O(n^3)$.


\item%(b)

To retrieve the sequence, we need to go deeper into the guts of the
problem, and find a specification of the optimal substructure of the
``negative-weight cycle'' problem.  First, let's define, similar to
above, $w_{ij} = -\log R[i,j]$; clearly, $w_{ii} = 0$ for all $i$, and
we can say that $w_{ij} = \infty$ if $R[i,j] = 0$.  We will be working
with iterated matrices $D^{(k)}$ and $\Pi^{(k)}$, with components
$d^{(k)}_{ij}$ and $\pi^{(k)}_{ij}$, respectively; $D^{(k)}$
represents the all-pairs shortest paths among nodes $1 \rdots k$, and
$\Pi^{(k)}$ is the associated predecessor matrix.

Let us assume that there is no negative-weight cycle among nodes
$1 \rdots k-1$.  (In the base case, this is trivially satisfied when
$k = 2$, since $w_{11} = 0$.)  Then, it is clear that if there exists
a negative-weight cycle among nodes $1 \rdots k$, node $k$ is in that
cycle.  (Without loss of generality, we can take the cycle to be a
simple cycle, for if there exists any negative-weight cycle, there
must exist a simple negative-weight cycle containing $k$.)  If the
successor and predecessor of $k$ in the cycle are nodes $i$ and $j$,
then the cycle formed by concatenating the edge $(k,i)$, a shortest
path from $i$ to $j$, and the edge $(j,k)$ must have smaller weight
than our original cycle, and thus must also be a negative-weight
cycle.  Thus, we can conclude that, if there exists a negative-weight
cycle in $1 \rdots k$, then, for some nodes $i,j \in \{1,\dots,k-1\}$,
we have $w_{ki} + d^{(k-1)}_{ij} + w_{jk} < 0$.  The converse is, of
course, trivially true.  Thus, we have created a test for the creation
of negative-weight cycles by adding one node (node $k$).

Of course, the above assumes the existence of the matrix $D^{(k)}$; it
remains to be shown by that matrix can be kept updated as we add nodes
to the graph.  Since the algorithm will return success upon finding a
negative-weight cycle, we can assume we only need to generate
$D^{(k)}$ from $D^{(k-1)}$ when it is found that there are no negative
cycles among the nodes $1 \rdots k$.

Under that assumption, a shortest path from any node
$i \in \{1, \dots, k-1\}$ to node $k$ must consist of a shortest path
(among nodes $1 \rdots k-1$) from node $i$ to a node $j$, concatenated
with the edge $(j,k)$.  Thus,
$d^{(k)}_{ik} = \min \left\{ d^{(k-1)}_{ij} + w_{jk}
                      \mbox{\ for all\ } j \in \{1 \rdots k-1\} \right\}$
(note that, since $d^{(k-1)}_{ii} = 0$, this takes into account the
possibility that the shortest path is a single edge).  Similarly,
$d^{(k)}_{ki} = \min \left\{ w_{kj} + d^{(k-1)}_{ji}
                      \mbox{\ for all\ } j \in \{1 \rdots k-1\} \right\}$.

Finally, for any nodes $i,j \in \{ 1 \rdots k-1 \}$, we need to
generate $d^{(k)}_{ij}$.  There are two cases:  either the shortest
path between $i$ and $j$ does not pass through $k$, in which case
$d^{(k)}_{ij} = d^{(k-1)}_{ij}$; or the new shortest path does pass
through $k$, in which case it can be decomposed into two shortest
subpaths, from $i$ to $k$, and from $k$ to $j$, and hence
$d^{(k)}_{ij} = d^{(k)}_{ik} + d^{(k)}_{kj}$.  Thus, in conclusion, we
have
$$ d^{(k)}_{ij} = \min\(d^{(k-1)}_{ij}, d^{(k)}_{ik} + d^{(k)}_{kj}\) $$

The algorithm based on these dynamic programming recursions is fairly
simple, ultimately; the only addition to the steps outlined is the
creation of the predecessor matrix $\Pi^{(k)}$, which behaves exactly
as one might expect.  It is used to regenerate the negative-weight
cycle, at the end.

\vbox{
\begin{program}
|Print-Negative-Weight-Cycle|(W)
\quad\tab d^{(1)}_{11} \gets 0
          \pi^{(1)}_{11} \gets |nil|
          \FOR k \gets 2 \rdots n
              \FOR i \gets 1 \rdots k-1
                  \FOR j \gets 1 \rdots k-1
                      \IF w_{ki} + d^{(k-1)}_{ij} + w_{jk} < 0
                         \THEN |Print|(k)
                               |Print-All-Pairs-Shortest-Path|(\Pi, i, j)
                               \RETURN \TRUE
                               \untab%
                         \untab%
                      \untab%
                  \untab%
              d^{(k)}_{kk} \gets 0
              \pi^{(k)}_{kk} \gets |nil|
              \FOR i \gets 1 \rdots k-1
                  d^{(k)}_{ik} \gets \infty
                  \pi^{(k)}_{ik} \gets |nil|
                  \FOR j \gets 1 \rdots k-1
                      \IF d^{(k)}_{ik} > d^{(k-1)}_{ij} + w_{jk}
                         \THEN d^{(k)}_{ik} \gets d^{(k-1)}_{ij} + w_{jk}
                               \pi^{(k)}_{ik} \gets j
                               \untab%
                         \untab%
                      \untab%
                  \untab%
              \FOR i \gets 1 \rdots k-1
                  d^{(k)}_{ki} \gets \infty
                  \pi^{(k)}_{ki} \gets |nil|
                  \FOR j \gets 1 \rdots k-1
                      \IF d^{(k)}_{ki} > w_{kj} + d^{(k-1)}_{ji}
                         \THEN d^{(k)}_{ki} \gets w_{kj} + d^{(k-1)}_{ji}
                               \IF i = j
                                  \THEN \pi^{(k)}_{ki} \gets k
                                  \ELSE \pi^{(k)}_{ki} \gets \pi^{(k-1)}_{ji}
                                       \untab%
                                  \untab%
                               \untab%
                         \untab%
                      \untab%
                  \untab%
              \FOR i \gets 1 \rdots k-1
                  \FOR j \gets 1 \rdots k-1
                      \IF d^{(k-1)}_{ij} < d^{(k)}_{ik} + d^{(k)}_{kj}
                         \THEN d^{(k)}_{ij} \gets d^{(k-1)}_{ij}
                               \pi^{(k)}_{ij} \gets \pi^{(k-1)}_{ij}
                         \ELSE d^{(k)}_{ij} \gets d^{(k)}_{ik} + d^{(k)}_{kj}
                               \pi^{(k)}_{ij} \gets \pi^{(k)}_{kj}
                               \untab%
                         \untab%
                      \untab%
                  \untab%
              \untab%
          \RETURN \FALSE
\end{program}
}

This pseudocode looks rather ugly and complicated, but it is a direct
transcription of the fundamental recursions of the problem.
Ultimately, the first segment of the main loop is the most important;
the rest is just bookkeeping to keep the all-pairs shortest-paths
matrices up-to-date.  The nested loop struture of the algorithm can be
easily shown by inspection to give a running time for the algorithm of
$O(n^3)$, which is as efficient as the (simpler) algorithm used in
part (a) to detect negative-weight cycles.

Since a negative-weight cycle on the graph with edge weights defined by
$W$ is equivalent to an arbitrage cycle using exchange rates $R$, this
algorithm prints out the correct sequence of currencies.

\end{enumerate}
\newpage



\end{document}
