\documentclass[12pt]{article}

\usepackage{geometry}
\newcommand{\myspan}{\mbox{span}}

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

\begin{enumerate}

\item \textbf{[20 Points] That Weird Inequality!}
 Consider an arbitrary graph $G = (V, E)$ and a matching $M$ in that graph.  Show that for any $U \subseteq V$
			\[
			|M| \leq \frac{1}{2}(|V| + |U| - o(G-U))
			\]
			where $G-U$ is the graph induced by removing the vertices in $U$ from $G$ and $o(G-U)$ denotes the number of connected components in $G-U$ that have  an
			odd number of vertices.

		
\item  \textbf{[35 Points]  Edmond's Algorithm Revisited.}
Recall that Edmond's Algorithm works like this:  Starting with a graph $G$ and some matching (starting with the empty matching is fine), label all of the unmatched vertices EVEN.  Then, begin a search from an EVEN node (a ``root'') until that search completes, before moving on to search from the next EVEN root.  When searching from an EVEN node $u$, proceed as follows:
	\begin{itemize}
		\item If there is an edge $(u, v)$ where $v$ is unlabelled, label $v$ ODD.  Since $v$ must be a matched vertex, follow the matched edge incident on $v$ to its matched neighbor $w$.  Label
		$w$ EVEN.  We have now extended our augmenting path ``forest''.
		\item If there is an edge $(u, v)$ where $v$ is labelled EVEN and $v$ was reached from a different root, then we have found an augmenting path.  Use that augmenting path to make the matching larger.  Then, expand any blossoms that got shrunk in order to bring this new matching back to the original graph $G$.  Finally, start this entire process from scratch using the new matching in our original graph $G$.
		\item If there is an edge $(u, v)$ where $v$ is labelled EVEN and $v$ was reached from the same root as $u$ then we have found a blossom.  Contract that blossom into a single vertex and label it EVEN.  Continue the search from that blossom node.
	\end{itemize}
	\begin{enumerate}
		\item At each step, the algorithm either increases the size of the augmenting path forest, finds an augmenting path and starts all over with the larger matching, or shrinks a blossom and continues searching.   If none of these cases can be applied, we \textbf{claim} that our matching is a maximum matching in the current graph (which is the original graph but with some blossoms possibly shrunk).  Prove this claim.  To do so, you'll need to appeal to the result of Problem~1 and choose $U$ to be the set of ODD labelled vertices.
		\item Explain why this matching, with the blossoms expanded and  ``every other edge'' in each blossom added to the matching as we expand, results in a maximum matching for the original graph $G$.  You may appeal to results that we've proved in class.
		\item Derive a polynomial-time upper bound on the worst-case running time of Edmond's Algorithm.
	\end{enumerate}	

\item  \textbf{[25 Points] The Tutte-Berge Formula and Tutte's Matching Theorem!}
The Tutte-Berge Formula is yet another min-max formula (like min cut-max flow, min vertex cover-max matching) and it states:
\[
			max_{M} |M| = \min_{U \subseteq V} \frac{1}{2}(|V| + |U| - o(G-U))
\]
	\begin{enumerate}
		\item Prove this inequality by using the correctness of Edmond's Algorithm from the previous problem.
		\item Tutte's Theorem states that a graph $G$ has a perfect matching (a matching of all vertices) iff for every set $U$, the number of 
		odd components of $G-U$ is at most $|U|$.  Prove it.
	\end{enumerate}

\item \textbf{[20 Points] Rank and Span Envy!}
	\begin{enumerate}
 		 \item 
	   Let $M=(E, \cal{I})$ be a matroid.  Analogous to the definition in a vector space, the 
            \emph{rank} of a set $X \subseteq E$, denoted $r(X)$, is the size of a largest independent
            subset of $X$.  Let $B$ be a basis of $M$.  Show that $r(B) = r(E) = |B|$.
            
 		 \item 
  	   Recall that if $V$ is a vector space and $X \subseteq V$, the \emph{span}
  	   of $X$, denoted $\myspan(X)$, is defined to be the subspace of all vectors that can be
	   expressed as a linear combination of vectors in $X$.  One property of vector spaces is that for
	   any basis $B$ in vector space $V$, $\myspan(B) = V$.
	   
	   If $M = (E, \cal{I})$ is a matroid and $X \subseteq E$, the span of $X$, denoted 
	   $\myspan(X)$, is defined to be a maximal superset $Y$ of $X$ such that $r(Y) = r(X)$.\footnote
	   {This means that $Y$ is a superset of $X$ but that no proper superset of $Y$ has rank equal to 
	   $r(X)$.}
	   Let $M = (E, \cal{I})$ be a matroid and let $B$ be a basis in the matroid.  Show that
	   $\myspan(B) = E$.
	\end{enumerate}

\end{enumerate}
\end{document}

