\documentclass[12pt]{article}

\input{cps130}

\begin{document}

\title{Bipartite Matching (17)}
\author{Michael L. Littman}
\date{October 29th, 1998}

\maketitle 

\section{MATCHING PROBLEM}

\subsection{Teaching Assignments}

\ni Every semester, the CS faculty has to figure out who is going to
teach what.

\ni We try to assign faculty to teach all the courses (one course per
professor, one professor per course), but if some important course
would go untaught, we bring in a grad student or local researcher to
help out, or have someone do double duty.

\ni So, it's important to do as good a job as possible at assigning
faculty to courses on the first try.

\subsection{Example Semester}

\ni Here's a piece of the data from a previous semester.  Some
professors are capable of teaching more than one course and some
courses can be taught by more than one professor.

\ni Courses: CPS130, CPS108, CPS100E, CPS100

\ul
\li Littman: CPS130
\li Rodger: CPS130, CPS100E
\li Astrachan: CPS108, CPS100E, CPS100
\li Ramm: CPS100E
\li Duvall: CPS100E
\el

\subsection{Bipartite Graphs}

\ni This problem is naturally expressed as a {\em bipartite\/} graph.

\ni Such a graph $G=(V,E)$ has a set of nodes $L$ and a set of nodes
$R$ such that $L \cap R = \emptyset$, $L \cup R = V$ (partition:
mutually exclusive and exhaustive), and for all $(u,v)\in E$, $u \in
L$ and $v \in R$.

\ni Also natural for machines-tasks, classes-classrooms, and others?

\ans{Boys-girls, senders-receivers, servers-clients,
clothes-bodyparts, meat-wine, etc.}

\subsection{Matching}

\ni A {\em matching\/} $M$ in a graph $G=(V,E)$ is a subset of $E$
such that there is no $u\in V$, $v_1\in V$, $v_2\in V$ such that
$v_1\neq v_2$ and either $(u,v_1) \in M$ and $(u,v_2) \in M$, or
$(v_1,u) \in M$ and $(v_2,u) \in M$.

\ni In other words, no node is linked to two other nodes.  It's a
monogamy thing.

\ni I'll use ``blue'' edges to refer to those in the matching $M$ and
``white'' for the others.

\ni Example...

\subsection{Max Matchings}

\ni A {\em maximal\/} matching $M$ is a matching such that any other
edge in $E$ that might be added to $M$ will violate the matching
property (one or the other of the nodes is already matched).

\ni A {\em maximum\/} matching is the largest matching out of all
possible matchings.

\ni Clearly a maximum matching is maximal.  But is every maximal
matching maximum?

\ni Examples... Astrachan 100E, 108, 100/108

% 2: astrachan 100E
% 3: littman 130, astrachan 108, duvall 100
% 4: littman 130, astrachan 108, duvall/rodger 100E, astrachan 100
% owen does double duty
% easy proof that none can do all 4: both 108 and 100 require owen

\subsection{Finding a Max Matching}

\ni Easy to find a maximal matching.  Just keep adding edges until
we're full.  Running time?  (HW)

% \Theta(n+m): mark all vertices as unmatched (array).  Loop through
% the edges.  If both vertices unmatched, add edge to matching and
% mark endpoints as matched.

\ni Unfortunately, because not every maximal matching is maximum, we
can get stuck.

\ni What we really want is a maximum matching.  So how can we find
one?

\section{MIN-CUT MAX-FLOW}

\subsection{Augmenting Path}

\ni Turns out that we can actually take a non-maximum maximal matching
and extend it by changing the pairing of some of the nodes.

\ni An {\em augmenting path\/} starts at an unmatched node on the
left, then alternates taking white (unmatched) and blue (matched) edges
back and forth until an unmatched node on the right is reached.

\ni Example...

\subsection{Augmenting Path Facts}

\ni Augmenting paths are neat:

\ul

\li An augmenting path has one more white edge than blue.  Why?  

\ans{Start and end on white.}

\li Flipping the color of edges on the augmenting path results in a
valid matching.  Why?  

\ans{Turning a blue edge white could never hurt.  The new blue edges
all emanate from nodes with no blue edges (or formerly one blue edge,
now white).}

\li Therefore, after flipping the colors, our matching is bigger by
one edge.

\el

\subsection{Algorithm}

\ni We're getting close to an algorithm.

\begin{algorithm}{Bipartite-Match}{G}
M \= \emptyset \\
p \= \mbox{\sc Augmenting-Path}(G,M) \\
\begin{WHILE}{p \neq \mbox{\tt nil}}
 M \= M \cup p[1] \\
 \begin{FOR}{i \= 1 \TO (|p|-1)/2}
  M \= M - p[2i] \\
  M \= M \cup p[2i+1]
 \end{FOR} \\
 p \= \mbox{\sc Augmenting-Path}(G,M)
\end{WHILE} \\
\RETURN M
\end{algorithm}   

\ni Will get a matching that's maximal-plus-plus.  But, there are still
some unanswered questions.  Like?

\ans{How do we find an augmenting path?  Does no augmenting path imply
maximum?}

\subsection{Cuts}

\ni Break left and right vertices into top and bottom subsets.

\ni The {\em size\/} of a cut is the number of bottom left nodes $x$,
plus the number of top right nodes $y$, plus the number of edges from
top left to lower right $z$.

\ni {\bf Lemma:} The size $x+y+z$ of any cut is an {\em upper bound\/}
on the size of the maximum matching.

\ni Why?  Picture.

% \latex{\pagebreak}

\subsection{Max-flow Min-cut Theorem}

\ni Given a bipartite graph $G$ and a matching $M$, the following are
equivalent:

\ul

\li[(1)] The current matching is maximum.

\li[(2)] There are no augmenting paths.

\li[(3)] The size of the matching is equal to the size of some cut.

\el

\ni Proof:

\ul

\li (1) implies (2) because the existence of an augmenting path
implies that the current matching is {\em not\/} maximum.  So maximum
implies no augmenting path.

\li (3) implies (1) because of the lemma: the size of a cut upper
bounds the size of the matching, so if we have a matching that meets
this upper bound, it is maximum.

\li (2) implies (3) is the interesting one...

\el

\subsection{Proof of Max-flow Min-cut}

\ni Construct the following cut: Let the top nodes be the unmatched
left nodes along with all those nodes reachable by alternating
white-blue paths from them.  Let the bottom nodes be the others.

\ni Facts:

\ul

\li All $y$ top right nodes are matched.  What would it mean if a top
right node were unmatched?  

\ans{Augmenting path.}

\li All $x$ bottom left nodes are matched.  By definition... all
unmatched left nodes were put on top.

\li There are $z=0$ edges from top left to bottom right.  This is
because there can be no such edge.  Why?  Such an edge couldn't be
white, because any right node with a white edge from the top is itself
a top, by definition.  But, such an edge couldn't be blue, either,
because all top left nodes are either unmatched (the starter nodes),
or matched to a top right node (the others).

\el

\ni So, the size of this cut is equal to the size of the matching.
Therefore, we have a maximum matching, since cut sizes are upper
bounds on matching sizes.

% \latex{\pagebreak}

\section{FORD-FULKERSON METHOD}

\subsection{Review}

\ni So, {\sc Bipartite-Match} computes a maximum matching!

\ni But, how do we find augmenting paths?

\subsection{Augmenting-Path Algorithm}

\ni This is just another application of depth-first search (or
breadth-first).

\ul

\li Mark nodes as matched or unmatched.

\li Start a search from each of the unmatched left nodes.

\li Traverse white edges from left to right.

\li Traverse blue edges from right to left.

\li Stop successfully if an unmatched right node is reached.

\li Stop with failure if search terminates without finding an
unmatched right node.

\el

\ni Running time? 

\ans{$O((|V|+|M|)+(|V|+|E|)) = O(|V|+|E|)$.}


\subsection{Overall Running Time}

\ni Accounting:

\ul

\li Time before loop: $O(|V|+|E|)$.

\li Each iteration: $O(2|P|+(|V|+|E|)) = O(|V|+|E|)$.

\el

\ni Total time is time for initialization plus time for each iteration
times maximum number of iterations.  How many iterations?

\ans{$|V|/2$, since each augmenting path adds two nodes to the
matching.}

% \ans{Each search for an augmenting path is $\Theta(|V|+|E|)$; largest
% possible.}

\ni $O((|V|+|E|)+|V|(|V|+|E|)) = O(|V||E|)$ (best algorithm known is
$O(\sqrt{|V|}|E|)$.

% \latex{\pagebreak}

\section{GENERALIZATIONS}

\subsection{Network Flow}

\ni We can generalize the bipartite matching problem quite a bit.

\ni A beautiful generalization is network flow:

\ul

\li source, sink, nodes, capacities, flow.

\el

\ni Can be solved efficiently using a generalization of augmenting
paths: $O(|V||E|^2)$.

\ni Matching is a special case: unit capacities, flow left to right.


\subsection{Linear Programming}

\ni Even more general is linear programming (LP): $Ax \le b$, maximize
$cx$.

\ni Example:

\ul

\li One variable for each edge, constrained to be between zero (white)
and one (blue).

\li Constraint for each node: sum of value of variables on incident
edges must be no more than one (matching property).

\li Maximize sum of edges (number of edges in matching).

\el

\ni In spite of the lack of an integrality constraint, the value of
this linear program is equal to the size of the maximum matching.

\ni Can solve network flow problems this way, as well as some tricky
generalizations.

\ni Theoretically efficient LP algorithms (ellipsoid, interior point)
are very complex.  Practical LP algorithm (simplex) is inefficient in
the worst case.  Very good commercial implementations exist!

% \latex{\pagebreak}


\end{document}

