%% This LaTeX-file was created by <jl> Mon Mar 16 11:46:13 1998
%% LyX 0.12 (C) 1995-1998 by Matthias Ettrich and the LyX Team

%% Do not edit this file unless you know what you are doing.
\documentclass{article}
\usepackage[T1]{fontenc}

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\newcommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\spacefactor1000}

\makeatother

\begin{document}

3/16/98 day 18 ``We should stop.''


\section{Max flow}


\subsection{definitions}

\begin{itemize}
\item Maximal flow = a flow which can't be improved without backtracking.
\item Maximum flow = a flow which can't be improved.
\end{itemize}

\subsection{Level graph}

A level graph is one which can have all of it's nodes arranged in levels s.t.
nodes at level \( l+1 \) don't connect to nodes in level \( l \). A level graph is a DAG (directed
acyclic graph). 


\subsection{Dinic}

To find the maximal flow (phase) do a depth first search through the DAG. Dinic
came up with an \( O(mn) \) per phase algorithm. \( \#phases\leq n \).


\subsection{MPM algorithm \protect\( O(n^{3})\protect \)}

\begin{itemize}
\item \( c(v)=min\{\sum _{u\in V}c(u,v),\sum _{u\in V}c(v,u)\} \) = the capacity of a vertex.
\end{itemize}
Within a phase, saturate a node, then push the flow into the other nodes. 


\subsubsection{code}

\begin{enumerate}
\item find min capacity vertex
\item if capacity(v) = u then delete v
\item push flow to sink and to source.
\end{enumerate}

\subsubsection{data structure}

We meed a data structure to operate with:

\( \begin{array}{cccc}
 & \#/phase & cost & total\\
delete & n & log(n) & n*log(n)\\
min & n & 1 & n\\
decrement & n^{2} & 1 & n^{2}
\end{array} \)

Actually, arrays work just as well


\subsubsection{timing analyses}

If an edges is saturated associate the cost of saturation with the edge. Since
there are \( m \) edges which will only saturate at most once, the cost of all saturated
edges \( \leq m\leq n^{2}\leq n^{3} \).


\section{Example problems}


\subsection{Maximum matching problem}

There are two groups 'boys' and 'girls'. Each boy-girl pair has some 'compatibility
rating'. The goal is to match boys to girls, maximizing overall 'compatibility'.
The problem can be turned into a maximum flow problem. Make a source connect
to all boys, the boys connect to the girls, and the girls connect to the sink.
All edges have capacity 1, which means each 'boy' will connect to 1 'girl'.


\subsubsection{Maximum matching}

The algorithm can be specialized to \( O(m\sqrt{n}) \). 

\begin{itemize}
\item Cost per phase is \( O(m) \) 
\item \#phases is \( O(\sqrt{n}) \)
\end{itemize}
Let \( M \) = matches, \( M^{*} \) = maximal match.

\( M\bigoplus M^{*}=(M-M^{*})\cup (M^{*}-M) \) = an augmenting path.

All the augmenting paths are disjoint in the maximum matching problem. Do depth
first search. When you encounter the sink, pop the stack and remove the searched
edges then start over. Each edges is only searched over once so the cost per
phase is \( O(m) \). With \( \sqrt{n} \) phases completed, \( \#levels\geq \sqrt{n} \). \( M\bigoplus M^{*}=K \) vertex disjoint paths from s to t.
Length \( \geq \sqrt{n} \) which implies that \( K\leq \sqrt{n} \).


\subsection{Maximum number of disjoint paths}

Find the maximum number of edges disjoint paths from a source to a sink. Setup
each edge in the graph to have capacity one and solve for the max flow, which
will be composed of some number of disjoint paths.


\subsection{Maximum number of vertex disjoint paths}

Find the maximum number of vertex disjoint paths. Split all vertices into 2
nodes. The first node has all the incoming edges and connects to the other node.
The other node has all the outgoing edges of the original vertex. Now, any flow
must go between the 2 nodes and only one flow can go between them which means
flows are vertex disjoint.

\end{document}