\documentclass[12pt]{article}

\usepackage{geometry}

\begin{document}
	\begin{center}
	\bf
	Advanced Topics in Algorithms \\
	Computer Science 182b\\
	Spring 2011\\
	\rm
	Homework 1\\
	Due  Wednesday, January 26  \\
\end{center}

\begin{enumerate}

\item \textbf{[25 Points]  Professor Lai's Greedy Matching Algorithms.}
Professor I.~Lai of the Pasadena Institute of Technology is giving a colloquium talk at Harvey Mudd.
	\begin{enumerate}
		\item Prof.~Lai begins the lecture this way.  ``That algorithm that Prof.~Ran showed in class for unweighted bipartite graphs is nice, but it's too complicated and too slow.  I have a much simpler and faster greedy algorithm!  The algorithm simply chooses an arbitrary edge and places it in the matching.  Then, it chooses another edge that has no vertex in common with the previously chosen edge.  It repeatedly chooses an arbitrary edge that has no vertices in common with any previously chosen edge until no such edge exists.  Greed rocks!''
		\begin{enumerate}
			\item Give a simple counterexample that shows that Prof.~Lai's algorithm does not necessarily find a maximum matching.
			\item Prove that Professor Lai's algorithm is guaranteed to find a matching whose size at least one half the optimal size!  (That's neat - it's an approximation algorithm!)
			\item Show that the ratio of one half is tight by describing how arbitrarily large graphs can be constructed such that Prof.~Lai's algorithm may construct solutions whose size is exactly one half the maximum size.
			\item Describe a fast implementation of Lai's algorithm and derive its asymptotic running time.
		\end{enumerate}
		\item Next, Prof.~Lai says.   ``Aha!  Very nice work clever Mudders.  Now, let's consider weighted bipartite graphs  (specifically, fully connected bipartite graphs $K_{n, n}$ with positive edge weights).  The objective is to find a perfect matching of maximum weight.  My algorithm sorts the edges by decreasing edge weight.  Then, it chooses edges from this sorted list, one-by-one, adding an edge if it doesn't share a vertex with any previously chosen edge.  I think that this algorithm will always  find a matching whose total weight is at least half of the maximum weighted matching.''  State whether this claim is true or false and prove your claim.
	\end{enumerate}

\item \textbf{[25 Points]  A Game on Graphs!}
Here's a fun 2-player game played on a general undirected graph (i.e. the graph is not necessarily bipartite).
Player 1 chooses some vertex $v_1$ and marks it.  Player 2 then chooses an unmarked vertex $v_2$ adjacent to $v_1$ and marks it. Player 1 now chooses an unmarked vertex $v_3$ adjacent to $v_2$, etc.
In other words, the two players alternate play  such that the sequence of vertices $v_1, v_2, \dots, v_k$ (chosen in that order) forms a simple (i.e. cycle-free)  path in the graph.  The last player able to select a vertex wins.
Prove that the first player has a winning strategy if the graph has no perfect matching and the second player has a winning strategy if the graph has a perfect matching.
As we'll see next week, there is a polynomial-time algorithm for finding a maximum matching in a general graph and thus this algorithm can determine whether or not a graph has a perfect matching.
(For those of you who took Complexity Theory in the fall, this looks remarkably similar to the Generalized Geography game that we proved was PSPACE-complete.  You might ask yourself how we can reconcile
the PSPACE-completeness of Generalized Geography with this result.)

\item \textbf{[25 Points] Bipartite Graph Matching.}  Consider a bipartite graph with bipartition $X$, $Y$.   We say that $M$ is a matching of $X$ \emph{into} $Y$ if $M$ matches every vertex of $X$.  In this problem, you will prove a famous result that states precisely when there exists a matching of $X$ into $Y$. For any $S \subseteq X$, let $N(S)$ denote the set of neighbors of $S$.  Your task is to prove that a bipartite graph has a matching of $X$ into $Y$ if and only if $|N(S)| \geq |S|$ for all $S \subseteq X$.

One direction of this statement will be very easy to prove!
There are a number of ways to prove the harder direction.  The approach that I would like you to use here starts like this.   Assume that $|N(S)| \geq |S|$ for all $S \subseteq X$ but that a maximum matching $M$ in the graph leaves one or more vertices in $X$ unmatched (or ``unsaturated'').  Then, we wish to construct a set $S \subseteq X$ such that $|N(S)|  <  |S|$ in order to obtain a contradiction.  To this end, let $x \in X$ be an unsaturated vertex with respect to $M$ (also called ``$M$-unsaturated'').  Let $S$ and $T$ be the sets of vertices in $X$ and $Y$, respectively, that are reachable from $x$ by $M$-alternating paths.  Now, show that $S$ has the desired property, leading to a contradiction.

\item \textbf{[25 Points] A Min-Max Theorem.}  Recall that we mentioned in class that the size of a smallest vertex cover in a bipartite graph is equal to the size of a maximum matching in that graph.  We proved this result using the Max Flow-Min Cut Theorem, but now you will prove it more directly using the theorem that you just proved above.  In particular, your proof should begin by positing a minimum vertex cover $C$.  This vertex cover will contain some vertices in $X$ and some vertices in $Y$.  Describe a simple construction of a matching from this vertex cover, and then appeal to the theorem in the previous problem to prove that this is a maximum matching.  
\end{enumerate}
\end{document}

