% This document is designed for amsmath with latex2e. % \documentclass[12pt,titlepage]{article} \usepackage{amsmath,amsthm,latexsym} \setlength{\topmargin}{-.4in} \setlength{\textheight}{9in} \setlength{\textwidth}{6in} \setlength{\oddsidemargin}{0in} \setlength{\evensidemargin}{0in} \setlength{\parskip}{.4\baselineskip} \renewcommand{\baselinestretch}{1.2} \newenvironment{myproof} {\begin{proof}[\textbf{\upshape Proof}]} {\end{proof}} \newcommand{\mybeginproof}{{\flushleft \textbf{Proof.~~}}} \newcommand{\myendproof}{\hfill $\Box$} \newcommand{\myendproofaftermath}{\hfill $\Box$} %\newtheorem{Theorem}{Theorem}[section] \newtheorem{Theorem}{Theorem} \newtheorem{Lemma}[Theorem]{Lemma} \newtheorem{Corollary}[Theorem]{Corollary} \newcommand{\mb}{\mbox} % \newcommand{\pO}{\textnormal{O}} \newcommand{\pO}{\textup{O}} \newcommand{\card}[1]{{\left| #1 \right|}} \newcommand{\eqa}{=^*} \newcommand{\greedynum}{\gamma} \newcommand{\half}{\frac{1}{2}} \newcommand{\heap}{\overline{K}} \newcommand{\matchnum}{\nu} \newcommand{\mindeg}{\delta} \newcommand{\nextst}[1]{\hat{#1}} \newcommand{\bibsqr}[1]{\mbox{$\sqrt{{#1}}$}} \begin{document} % page header \pagestyle{myheadings} \markright{\sc the electronic journal of combinatorics \textbf{4} (1997) \#R25\hfill} \bibliographystyle{plain} \begin{titlepage} \begin{center} \textbf{ AN EXACT PERFORMANCE BOUND FOR AN $\mathbf{\pO (m+n)}$ TIME \\ GREEDY MATCHING PROCEDURE} \\[2.5ex] Andrew Shapira \\[2.5ex] ECSE Department \\ Rensselaer Polytechnic Institute \\ Troy, New York 12180 \\ \verb=shapiraa@cs.rpi.edu= \\[2.5ex] Submitted July 20, 1997; accepted October 15, 1997. \\[10ex] \end{center} \textbf{AMS Subject Classification (1991).} Primary: 05C70. Secondary: 68Q25, 05C35, 05C85, 68R05, 68R10. \\[2.5ex] % 05 Combinatorics % 05C Graph Theory % 05C35 Extremal Problems % 05C70 Factorization, Matching, Covering, and Packing % 05C85 Graph Algorithms %68 Computer Science % 68R Discrete Mathematics in Relation to Computer Science % 68R05 Combinatorics % 68R10 Graph Theory % 68Q Theory of Computing % 68Q25 Analysis of Algorithms \textbf{Key Words.} Analysis of algorithms, extremal problems, greedy procedure, matching algorithms, matching heuristics, maximum matching, performance guarantees. \\[2.5ex] \textbf{Abstract.} We prove an exact lower bound on $\greedynum(G)$, the size of the smallest matching that a certain $\pO(m+n)$ time greedy matching procedure may find for a given graph $G$ with $n$ vertices and $m$ edges. The bound is precisely Erd\"{o}s and Gallai's extremal function that gives the size of the smallest maximum matching, over all graphs with $n$ vertices and $m$ edges. Thus the greedy procedure is optimal in the sense that when only $n$ and $m$ are specified, no algorithm can be guaranteed to find a larger matching than the greedy procedure. The greedy procedure and augmenting path algorithms are seen to be complementary: the greedy procedure finds a large matching for dense graphs, while augmenting path algorithms are fast for sparse graphs. Well known hybrid algorithms consisting of the greedy procedure followed by an augmenting path algorithm are shown to be faster than the augmenting path algorithm alone. The lower bound on $\greedynum(G)$ is a stronger version of Erd\"{o}s and Gallai's result, and so the proof of the lower bound is a new way of proving of Erd\"{o}s and Gallai's result. \end{titlepage} \section{Introduction} The following procedure is sometimes recommended for finding a matching that is used as an initial matching by a maximum cardinality matching algorithm~\cite{MoretShapiro}. Start with the empty matching, and repeat the following step until the graph has no edges: remove all isolated vertices, select a vertex $v$ of minimum degree, select a neighbor $w$ of $v$ that has minimum degree among $v$'s neighbors, add $\{v,w\}$ to the current matching, and remove $v$ and $w$ from the graph. This procedure is referred to in this paper as ``the greedy matching procedure'' or ``the greedy procedure.'' In the worst case, the greedy procedure performs poorly. For all $r \geq 3$, a graph $D_r$ of order $4r+6$ can be constructed such that the greedy procedure finds a matching for $D_r$ that is only about half the size of a maximum matching~\cite{ShapiraGreedyMatchingC}. This performance is as poor as that of any procedure that finds a maximal matching. On the other hand, there are classes of graphs for which the greedy procedure always finds a maximum matching~\cite{ShapiraGreedyMatchingC}. Furthermore, using a straightforward kind of priority queue that has one bucket for each of the $n$ possible vertex degrees, the greedy procedure can be made to run in $\pO(m+n)$ time and storage for a given graph with $n$ vertices and $m$ edges~\cite{ShapiraGreedyMatchingA}. The $\pO(m+n)$ running time is asymptotically faster than the fastest known maximum matching algorithm for general graphs or bipartite graphs~\cite{ABMP,Blum:ICALP90,FederMotwani:stoc91,Galil,HK,LovaszPlummer, MicaliVazirani,PapaSteig}. The greedy procedure's success on some graphs, $\pO(m+n)$ time and storage requirements, low overhead, and simplicity motivate the investigation of its performance. The matching found by the greedy procedure may depend on how ties are broken. Let $\greedynum(G)$ be the size of the smallest matching that can be found for a given graph $G$ by the greedy procedure, i.e., $\greedynum(G)$ is the worst case matching size, taken over all possible ways of breaking ties. We will show that each graph $G$ with $n$ vertices and $m \geq 1$ edges satisfies \begin{equation} \label{eq:introeq} \greedynum(G) \geq \min ( \left\lfloor n + \half - \sqrt{n^2 - n - 2m + \frac{9}{4}} \right\rfloor , \left\lfloor \frac{3}{4} + \sqrt{ \frac{m}{2} - \frac{7}{16} } \right\rfloor ). \end{equation} It will become clear that this bound is the best possible --- when only $n$ and $m$ are given, no algorithm can be guaranteed to find a matching larger than that found by the greedy procedure. The simpler but looser bound of $\greedynum(G) \geq m/n$ is proved in~\cite{ShapiraGreedyMatchingA}. The bound in~\eqref{eq:introeq} can be considered alone, or in conjunction with augmenting path algorithms --- the fastest known algorithms for finding a maximum matching. All known worst-case time bounds for augmenting path algorithms are $\omega(m+n)$. It is traditional to use a hybrid algorithm: first, use the greedy procedure (or one like it) to find a matching $M$ in $\pO(m+n)$ time; then, run an augmenting path algorithm with $M$ as the initial matching. We will see that~\eqref{eq:introeq} supports the use of such hybrid algorithms. Intuitively, if the input graph is dense, then the greedy procedure finds a large matching, and the augmenting path algorithm needs only a few augmentation phases; if the input graph is sparse, then each augmentation phase is fast. We can abstract the following technique for solving maximum cardinality matching problems: use one kind of method (perhaps the greedy procedure) for handling dense graphs, and another kind of method (perhaps an augmenting path algorithm) for handling other graphs. It may be interesting to investigate whether existing matching algorithms can be improved upon by explicitly using this technique. An outline of the remainder of this paper is as follows. Section~\ref{sec:definitions} contains definitions and notation. Section~\ref{sec:related} gives a theorem due to Erd\"{o}s and Gallai; our results are closely related to this theorem. Section~\ref{sec:guarantee} proves~\eqref{eq:introeq} and some variants of~\eqref{eq:introeq}. (This is a new way of proving Erd\"{o}s and Gallai's theorem.) Section~\ref{sec:hybrid} discusses the hybrid approach that uses the greedy procedure followed by an augmenting path algorithm. \section{Definitions and Notation} \label{sec:definitions} We consider the problem of finding a maximum matching in finite simple undirected unweighted possibly non-bipartite graphs. Let $G=(V,E)$ be a graph. We use $vw$ as an abbreviation for an edge $\{ v , w \} \in E$. For $v \in V$, the graph $G-v$ is the graph with vertex set $V-v$, and edge set $\{ xy \in E : x \neq v~\mbox{and}~y \neq v \}$. The number of vertices and edges in $G$ are respectively $n(G)$ and $m(G)$. The degree of a minimum degree vertex of $G$ is denoted $\mindeg(G)$. An edge $vw \in E$, $\deg v \leq \deg w$, is called \emph{semi-minimum} if $\deg v = \mindeg ( G )$ and $\deg w$ is minimum over the degrees of $v$'s neighbors. The matching number of $G$ is denoted by $\matchnum(G)$, i.e., $\matchnum(G)$ is the size of a maximum matching for $G$. The \emph{complete graph} on $n$ vertices is $K_n$; its complement is the \emph{heap} $\heap_n$. Function arguments are sometimes omitted when the context is clear, e.g., $\matchnum$ may be used instead of $\matchnum(G)$. The notation $a \eqa b$ indicates that some algebraic manipulation showing that $a=b$ has been omitted so as to shorten the presentation. \section{A Related Theorem} \label{sec:related} This paper's analysis of the greedy matching procedure is closely related to the following theorem. \begin{Theorem}[Erd\"{o}s and Gallai, 1959] \label{thm:erdosgallai} The maximum number of edges in a simple graph of order $n$ with a maximum matching of size $k$ ($2 \leq 2k \leq n$) is \begin{equation*} \left\{ \begin{array}{ll} \binom{k}{2}+k(n-k) \quad & ~\mbox{if}~k < \frac{2n-3}{5}, \\ \binom{2k+1}{2} \quad & ~\mbox{if}~\frac{2n-3}{5} \leq k < \frac{n}{2}, \\ \binom{2k}{2} \quad & ~\mbox{if}~k = \frac{n}{2}. \\ \end{array} \right. \end{equation*} \end{Theorem} Erd\"{o}s and Gallai's theorem can be proved in one direction by considering three graphs: the graph obtained by connecting every vertex of $K_k$ to every vertex of $\heap_{n-k}$; the graph $K_{2k+1}$; and the graph $K_n$. The edge counts appearing in the theorem are the number of edges in these graphs. Thus the indicated edge counts can be realized for a given value of $k$. Proving the theorem in the other direction is more involved~\cite{Berge,ErdosGallai1959}. The proof of our main result (Theorem~\ref{thm:greedyk} in Section~\ref{sec:guarantee}) is based on the greedy procedure. Since Theorem~\ref{thm:greedyk} implies Theorem~\ref{thm:erdosgallai}, the proof of Theorem~\ref{thm:greedyk} is a new way of proving Erd\"{o}s and Gallai's result. Theorem~\ref{thm:erdosgallai} implies that if a graph has more than the indicated number of edges as a function of $k-1$, then the matching number of the graph is at least $k$. This fact, which is essentially equivalent to Theorem~\ref{thm:erdosgallai}, is stated explicitly below. \begin{Corollary} \label{cor:erdosgallai} Let $G$ be a graph with $n$ vertices and $m$ edges, and let $k$ be an integer such that \begin{equation*} m \geq \left\{ \begin{array}{ll} \binom{k-1}{2}+(k-1)(n-k+1)+1 \quad & ~\mbox{if}~k \leq \frac{2n+2}{5}, \\ \binom{2k-1}{2}+1 \quad & ~\mbox{if}~k \geq \frac{2n+2}{5}. \end{array} \right. \end{equation*} Then $\matchnum(G) \geq k$. \end{Corollary} (In Corollary~\ref{cor:erdosgallai}, when $k = \frac{2n+2}{5}$, both conditions apply; they are equivalent.) The edge counting functions that appear in Corollary~\ref{cor:erdosgallai} are prominent in our analysis. In the remainder of this section we explicitly name these functions and establish some basic facts about them. Let %\begin{align} %f(r) & = \frac{(r-1)(r-2)}{2} + (r-1)(n-r+1) + 1 \notag \\ %& = \big( r-1 \big) \big( n - \frac{r}{2} \big) + 1, \\ %g(r) & = \frac{(2r-1)(2r-2)}{2} + 1 \notag \\ %& = \big( r-1 \big) \big( 2r-1 \big) + 1. %\end{align} \begin{equation} \begin{array}{rcccl} f(n,r) & = & \frac{(r-1)(r-2)}{2} + (r-1)(n-r+1) + 1 & = & \big( r-1 \big) \big( n - \frac{r}{2} \big) + 1,~\mbox{and}\\ g(n,r) & = & \frac{(2r-1)(2r-2)}{2} + 1 & = & \big( r-1 \big) \big( 2r-1 \big) + 1. \end{array} \end{equation} For fixed $n$, the functions $f(r)=f(n,r)$ and $g(r)=g(n,r)$ are functions of a real argument $r$, with $f(r)$ increasing on $[- \infty,n]$, $g(r)$ increasing on $[1,\infty]$, and, if $n \geq 2$, \begin{align} \label{eq:glessf} f(r) \geq g(r) \qquad & \mbox{for $1 \leq r \leq \frac{2n+2}{5}$}, \\ \label{eq:ggeqf} f(r) = g(r) \qquad & \mbox{for $r = \frac{2n+2}{5}$}, \\ \label{eq:ggreatf} g(r) \geq f(r) \qquad & \mbox{for $r \geq \frac{2n+2}{5}$}. \end{align} Define $b(n,r)$ by \begin{equation} \label{eq:bdef} b(n,r) = \left\{ \begin{array}{ll} f(n,r) \quad & \mbox{if $r \leq \frac{2n+2}{5}$}, \\ g(n,r) \quad & \mbox{if $r \geq \frac{2n+2}{5}$}. \end{array} \right. \end{equation} For fixed $n \geq 2$, $b(r)=b(n,r)$ is increasing on $[2,n]$, since $f(r)$ and $g(r)$ are. Also, \begin{equation} b(n,r) = \max ( f(n,r), g(n,r) ) \qquad \mbox{when $n \geq 2$ and $r \geq 1$}. \end{equation} \section{Performance Guarantees} \label{sec:guarantee} The following performance guarantee for the greedy matching procedure is the main result of the paper. \begin{Theorem} \label{thm:greedyk} Let $G$ be a graph with $n$ vertices and $m$ edges, and let $k$ be an integer such that \begin{equation*} m \geq \left\{ \begin{array}{ll} \binom{k-1}{2} + (k-1)(n-k+1)+1 \quad & \mbox{if $k \leq \frac{2n+2}{5}$}, \\ \binom{2k-1}{2} + 1 \quad & \mbox{if $k \geq \frac{2n+2}{5}$}. \end{array} \right. \end{equation*} Then $\greedynum(G) \geq k$. \end{Theorem} Later in this section we will derive~\eqref{eq:introeq} from Theorem~\ref{thm:greedyk}. We now establish two lemmas, and then use them to prove Theorem~\ref{thm:greedyk}. \begin{Lemma} \label{lemma:smallk} Let $G$ be a graph with $n$ vertices and $m$ edges, and let $k \leq 2$ be an integer such that \begin{equation*} m \geq \left\{ \begin{array}{ll} \binom{k-1}{2} + (k-1)(n-k+1)+1 \quad & \mbox{if $k \leq \frac{2n+2}{5}$}, \\ \binom{2k-1}{2} + 1 \quad & \mbox{if $k \geq \frac{2n+2}{5}$}. \end{array} \right. \end{equation*} Then $\greedynum(G) \geq k$. \end{Lemma} \begin{myproof} Assume the hypotheses of the lemma. The conclusion is trivial for $k \leq 0$. The case $k=1$ is also easy to verify. For $k=2$, we first want to show that \begin{equation} \label{eq:qpfour} m \geq n \geq 4. \end{equation} If $k = 2 \leq \frac{2n+2}{5}$, then $n \geq 4$, and \begin{equation*} m \geq \binom{2-1}{2} + (2-1)(n-2+1)+1 = n. \end{equation*} If $k=2 \geq \frac{2n+2}{5}$, then $n \leq 4$, and \begin{equation*} m \geq \binom{2 \cdot 2-1}{2} + 1 = 4, \end{equation*} implying that $n=4$. This establishes~\eqref{eq:qpfour}. Next, let $vw$ be a semi-minimum edge in $G$, with $\deg v = \mindeg(G)$, and $\deg w$ minimum over the degrees of $v$'s neighbors. Suppose for the purpose of contradiction that every edge in $G$ is incident on $v$, $w$, or both $v$ and $w$. Since $m \geq n$ and $\deg w \leq n-1$, there must exist some edge $vx$, $x \neq w$. The only possible vertices that $x$ can be adjacent to are $v$ and $w$, so $\deg x \leq 2$. This implies that $\deg w \leq 2$, by the minimality of $\deg w$ over the degrees of $v$'s neighbors. It also implies that $\deg v \leq 2$, by the minimality of $\deg v$. Therefore, $m \leq \deg v + \deg w - 1 \leq 3$, contradicting the fact that $m \geq 4$. It follows that $G$ contains some edge that is incident on neither $v$ nor $w$. Thus $G-v-w$ has at least one edge, and $\greedynum(G) \geq 2 = k$. \end{myproof} \begin{Lemma} \label{lemma:isolated} Let $i$, $j \geq i$, and $k$ be positive integers. Then $b(j,k) \geq b(i,k)$. \end{Lemma} \begin{myproof}~\\ \emph{Case I:} $k \geq \frac{2j+2}{5}$. Then $k \geq \frac{2i+2}{5}$, and \begin{equation*} b(j,k) = g(j,k) = (k-1)(2k-1)+1 = g(i,k) = b(i,k). \end{equation*} \emph{Case II:} $k \leq \frac{2j+2}{5}$ and $k \leq \frac{2i+2}{5}$. We have \begin{equation*} b(j,k) = f(j,k) = (k-1)(j-k/2)+1 \geq (k-1)(i-k/2)+1 = f(i,k) = b(i,k). \hspace{-1em} % kludge because latex adds too much space after above line \end{equation*} \emph{Case III:} $k \leq \frac{2j+2}{5}$ and $k \geq \frac{2i+2}{5}$. Then \begin{align*} \frac{2j+2}{5} & \geq k, \\ j-\frac{k}{2} & \geq 2k-1, \\ (k-1)(j-k/2)+1 & \geq (k-1)(2k-1)+1, \\ f(j,k) & \geq g(i,k), \\ b(j,k) & \geq b(i,k). \end{align*} \vspace{-.3in} \end{myproof} Now we can prove Theorem~\ref{thm:greedyk}. \noindent \textbf{Theorem 3 (Restatement and Proof).} Let $G$ be a graph with $n$ vertices and $m$ edges, and let $k$ be an integer such that \begin{equation*} m \geq \left\{ \begin{array}{ll} \binom{k-1}{2} + (k-1)(n-k+1)+1 \quad & \mbox{if $k \leq \frac{2n+2}{5}$}, \\ \binom{2k-1}{2} + 1 \quad & \mbox{if $k \geq \frac{2n+2}{5}$}. \end{array} \right. \end{equation*} Then $\greedynum(G) \geq k$. \begin{myproof} We will use induction on $k$. Lemma~\ref{lemma:smallk} is the base of the induction ($k \leq 2$). Fix $k \geq 3$, and suppose that for all $t < k$, all graphs $G$ with $m(G) \geq b(n(G),t)$ have $\greedynum(G) \geq t$. Let $H$ be a graph with \begin{equation} \label{eq:hedges} m(H) \geq b(n(H),k). \end{equation} The graph $H$ has at least one edge, because $b(n(H),k) \geq 1$. Let $G$ be the graph formed from $H$ by removing $H$'s isolated vertices. We have $\greedynum(G) = \greedynum(H)$, and the proof will be complete if we can show that $\greedynum(G) \geq k$. Since $n(H) \geq n(G)$ and $m(H) = m(G)$, Lemma~\ref{lemma:isolated} and~\eqref{eq:hedges} imply that $m(G) \geq b(n(G),k)$. Setting $n = n(G)$ and $m = m(G)$, we have \begin{equation} \label{eq:qstart} m \geq b(n,k). \end{equation} We will now discard $H$, and consider only $G$. The inequalities $m \geq b(n,k)$ and $k \geq 3$ together with~\eqref{eq:bdef} imply that \begin{equation} 3 \leq k \leq \frac{n}{2}. \end{equation} Let $vw$ be an arbitrary semi-minimum edge of $G$, with $\deg v = \mindeg = \mindeg(G)$, and $w$ having minimum degree among $v$'s neighbors. Set $\nextst{m} = m(G-v-w) = m - \mindeg - \deg w + 1$, and $\nextst{n} = n(G-v-w) = n-2$. By induction, it suffices to show that \begin{equation} \nextst{m} \geq b(n-2,k-1). \end{equation} Let us derive another inequality. The $\mindeg$ vertices adjacent to $v$ have degree $\deg w$ or more, and the $n-\mindeg$ vertices not adjacent to $v$ have degree $\mindeg$ or more. Therefore, \begin{align} m & \geq \half \Big( \mindeg \deg w + (n - \mindeg) \mindeg \Big) \notag \\ & = \half \mindeg \Big( n - \mindeg + \deg w \Big),~\mbox{so} \notag \\ \nextst{m} & \geq \half \mindeg \Big( n - \mindeg + \deg w \Big) - \mindeg - \deg w + 1 \notag \\ & = \half \mindeg \Big( n - \mindeg - 2 \Big) + \deg w \Big( \frac{\mindeg}{2}-1 \Big)+ 1. \label{eq:qeqn} \end{align} Now, several cases are considered. Some of the cases overlap. Cases where $k-1 \leq \frac{2(n-2)+2}{5}$ are indicated with an ``\emph{I}'' prefix; the cases where $k-1 > \frac{2(n-2)+2}{5}$ are indicated by ``\emph{II}.'' The goal is to show that $\hat{m} \geq b(n-2,k-1)$ in all cases. \emph{Case I:} $k-1 \leq \frac{2(n-2)+2}{5}$. We want to show that $\hat{m} \geq \big( k-2)\big( n-2-\frac{k-1}{2} \big) +1$, because $b(n-2,k-1)=f(n-2,k-1)=\big( k-2 \big) \big( n-2-\frac{k-1}{2} \big) +1$. \emph{Case I.A:} $\deg w \leq n+k-\mindeg-2$. Then \begin{equation} \label{eq:aonea} 0 \geq (\mindeg + \deg w - 1) - n - k + 3. \end{equation} Since $b(n,k) \geq f(n,k)$, by~\eqref{eq:qstart} we have \begin{equation} \label{eq:aoneb} m \geq \Big( k-1 \Big) \Big( n-\frac{k}{2} \Big) + 1. \end{equation} Adding~\eqref{eq:aonea} and~\eqref{eq:aoneb} gives \begin{align*} m & \geq \Big( k-1 \Big) \Big( n-\frac{k}{2} \Big) + 1 + \Big( \mindeg + \deg w - 1 \Big) - n - k + 3,~\mbox{so} \\ \nextst{m} & \geq \Big( k-1 \Big) \Big( n - \frac{k}{2} \Big) - n - k + 4 \\ % & = \Big( k-2 \Big) \Big( n - \frac{k}{2} \Big) - \frac{3k}{2} + 4 \\ % & = \Big( k-2 \Big) \Big( n - \frac{k}{2} - \frac{3}{2} \Big) + 1 \\ & \eqa \Big( k-2 \Big) \Big( n-2-\frac{k-1}{2} \Big) + 1. \end{align*} \emph{Case I.B:} $\mindeg > n-\frac{k}{2}-1$. In this case, $\mindeg \geq n - \frac{k}{2} - \half$. Reorganizing~\eqref{eq:qeqn}, and substituting for $\mindeg$, we have the following. \begin{align*} \nextst{m} & \geq \half \mindeg \Big( n - \mindeg + \deg w - 2 \Big) - \deg w + 1 \\ & \geq \half \Big( n - \frac{k}{2} - \half \Big) \Big( n + \Big( \deg w - \mindeg \Big) - 2 \Big) - \deg w + 1 \\ & \geq \half \Big( n - \frac{k}{2} - \half \Big) \Big( n - 2 \Big) - \deg w + 1 \\ % & = \Big( \frac{n}{2} - 1 \Big) \Big( n - \frac{k}{2} - \half \Big) % - \deg w + 1 \\ % & = \Big( \frac{n}{2} - 1 \Big) \Big( n - \frac{k}{2} - \frac{3}{2} \Big) % - \deg w + 1 + \frac{n}{2} - 1 \\ % & = \Big( \frac{n}{2} - 2 \Big)\Big( n-\frac{k}{2}-\frac{3}{2} \Big) % - \deg w + \frac{n}{2} + n - \frac{k}{2} - \frac{3}{2} \\ & \eqa \Big( \frac{n}{2} - 2 \Big)\Big( n-\frac{k}{2}-\frac{3}{2} \Big) + \Big( \frac{n}{2}-\frac{k}{2}-\frac{3}{2} \Big) + \Big( n- \deg w -1 \Big) + 1 \\ & \geq \Big( \frac{n}{2} - 2 \Big)\Big( n-2-\frac{k-1}{2} \Big) + 0 + 0 + 1 \\ & \geq \Big( k-2 \Big)\Big( n-2-\frac{k-1}{2} \Big) + 1. \end{align*} \emph{Case I.C:} $\deg w \geq n+k-\mindeg-1$ and $\mindeg \leq n-\frac{k}{2}-1$. Combining the inequalities $\deg w \geq n+k-\mindeg-1$ and $n-1 \geq \deg w$ yields \begin{equation} \mindeg \geq k. \label{eq:mindegsize} \end{equation} This will be used later. Next,~\eqref{eq:qeqn} gives \begin{align} \nextst{m} & \geq \half \mindeg \Big( n - \mindeg - 2 \Big) + \Big( n+k-\mindeg-1 \Big) \Big( \frac{\mindeg}{2} - 1 \Big) + 1 \notag \\ & \eqa \mindeg \Big( n - \mindeg + \frac{k}{2} - \frac{1}{2} \Big) - n - k + 2 \notag \\ & = y ( \mindeg ), \label{eq:qz} \end{align} where $y(t)$ is the function \begin{equation*} y(t) = t(n-t+\frac{k}{2}-\frac{1}{2})-n-k+2. \end{equation*} Now there are two sub-cases, according to the sign of \begin{equation} \label{eq:yderiv} y \prime (t) = n - 2 t + \frac{k}{2} - \frac{1}{2}. \end{equation} \emph{Case I.C1:} $\mindeg \leq \frac{n}{2} + \frac{k}{4} - \frac{1}{4}$. By~\eqref{eq:yderiv}, $y \prime (t) \geq 0$ for all $t \leq \mindeg$. Thus, from~\eqref{eq:mindegsize}, $y(\mindeg) \geq y(k)$, so by~\eqref{eq:qz}, we have $\hat{m} \geq y(k)$. Thus \begin{align*} \hat{m} & \geq y(k) \\ & \eqa \Big( k-2 \Big) \Big( n - 2 - \frac{k-1}{2} \Big) + 1 + \Big( n-k-2 \Big) \\ & \geq \Big( k-2 \Big) \Big (n - 2 - \frac{k-1}{2} \Big) + 1. \end{align*} \emph{Case I.C2:} $\frac{n}{2} + \frac{k}{4} - \frac{1}{4} \leq \mindeg \leq n-\frac{k}{2}-1$. By~\eqref{eq:yderiv}, $y \prime (t) \leq 0$ for $t \geq \mindeg$. Thus $y(\mindeg) \geq y ( n-\frac{k}{2}-1 )$. From~\eqref{eq:qz}, \begin{align*} \nextst{m} & \geq y(\mindeg) \\ & \geq y ( n-\frac{k}{2}-1 ) \\ & \eqa \Big( k-2 \Big) \Big( n - 2 - \frac{k-1}{2} \Big) + 1 + \Big( \frac{3n}{2} - \frac{7 k}{4} - \frac{10}{4} \Big) \\ & \geq \Big( k - 2 \Big) \Big( n - 2 - \frac{k-1}{2} \Big) + 1. \end{align*} \emph{Case II:} $k-1 > \frac{2(n-2)+2}{5}$. (This is equivalent to $k \geq \frac{2n+4}{5}$.) We want to show that $\hat{m} \geq (k-2)(2k-3)+1$, because $b(n-2,k-1)=g(n-2,k-1)=(k-2)(2k-3)+1$. \emph{Case II.A:} $\mindeg+\deg w \leq 4k-4$. We have $k \geq \frac{2n+4}{5} \geq \frac{2n+2}{5}$, so $b(n,k) = g(n,k)$, and \begin{align*} m & \geq g(n,k) \\ & = ( k-1 ) ( 2k-1 ) + 1 \\ & = 2k^2-3k+2 \\ & \geq 2k^2-7k+6+\mindeg + \deg w \\ & = ( k-2 ) ( 2k-3 ) + 1+ ( \mindeg+\deg w - 1 ),~\mbox{so} \\ \nextst{m} & \geq ( k-2 ) ( 2k-3 ) + 1. \end{align*} \emph{Case II.B:} $\mindeg + \deg w \geq 4k-3$ and $\mindeg \geq 2k-2$. As always, $n-1 \geq \deg w \geq \mindeg$ and $n \geq 2k$. By~\eqref{eq:qeqn}, \begin{align*} \nextst{m} & \geq \frac{1}{2} \mindeg ( n + ( \deg w - \mindeg ) - 2 ) - \deg w + 1 \\ & \geq \frac{1}{2} ( 2k-2 ) ( n -2 ) - \deg w+1 \\ & \eqa ( k-2 ) ( n-2 ) + ( -\deg w+1+n-2 ) \\ & \geq ( k-2 ) ( n-2 ) \\ & \geq ( k-2 ) ( 2k-3 ) +1. \end{align*} \emph{Case II.C:} $\mindeg + \deg w \geq 4k-3$ and $\mindeg \leq 2k-3$. Substituting into~\eqref{eq:qeqn} gives \begin{align} \nextst{m} & \geq \frac{1}{2} \mindeg \Big( n - \mindeg - 2 \Big) + \Big( 4k - 3 - \mindeg \Big) \Big( \frac{\mindeg}{2} - 1 \Big) + 1 \notag \\ & \eqa \frac{1}{2} \mindeg \Big( n - 2 \mindeg + 4 k - 5 \Big) - 4 k + \mindeg + 4 \notag \\ & \geq \frac{1}{2} \mindeg \Big( 2k - 2 \mindeg + 4 k - 5 \Big) - 4 k + \mindeg + 4 \notag \\ & = \mindeg \Big( 3k-\mindeg-\frac{5}{2} \Big) - 4 k + \mindeg + 4 \notag \\ & = z(\mindeg), \end{align} where $z(t)$ is the function \begin{equation*} z(t) = t ( 3k - t - \frac{5}{2} ) - 4 k + t + 4. \end{equation*} The derivative of $z(t)$ is $z \prime(t) = 3k-2t-3/2$, so \begin{equation*} z \prime ( t ) \leq 0~\mbox{for}~t \geq \frac{3k}{2} - \frac{3}{4}. \end{equation*} Now we will show that $\mindeg \geq \frac{3k}{2} - \frac{3}{4}$. We have \begin{align*} k & \geq \frac{2n+4}{5}, \\ \frac{5k}{2} & \geq n+2, \\ 4k-n-2 & \geq \frac{3k}{2} - \frac{3}{4}. \end{align*} By the definition of this case (II.C), \begin{equation*} \mindeg \geq 4k-3-\deg w \geq 4k-n-2 \geq \frac{3k}{2} - \frac{3}{4}. \end{equation*} Thus $3k/2-3/4 \leq \mindeg \leq 2k-3$, so $z \prime(t) \leq 0$ for all $t \geq \mindeg$. Therefore \begin{equation*} \hat{m} \geq z(\mindeg) \geq z(2k-3) \eqa (k-3)(2k-3) + 5k - \frac{19}{2} \geq (k-3)(2k-3)+1. \end{equation*} \end{myproof} Fix $n$ and $m$, and let $k_{\textrm{max}}$ be the maximum value of $k$ that satisfies Theorem~\ref{thm:greedyk} for the given values of $n$ and $m$. The theorem states that the greedy procedure finds a matching of size at least $k_{\textrm{max}}$. Given only $n$ and $m$, no algorithm can be guaranteed to find a matching of size greater than $k_{\textrm{max}}$, because by Erd\"{o}s and Gallai's theorem (Theorem~\ref{thm:erdosgallai}) there exists a graph on $n$ vertices and $m$ edges having matching number as small as $k_{\textrm{max}}$. When only $n$ and $m$ are given, then, the greedy procedure is optimal in the following sense: using $\pO(m+n)$ time and storage, it finds a matching of the maximum possible size that can be guaranteed for the given values of $n$ and $m$. We can reformulate Theorem~\ref{thm:greedyk} to have fewer variables by explicitly solving for $k_{\textrm{max}}$. To do this we need two lemmas. These lemmas can be proved using the quadratic formula; the proofs are omitted. The lemmas and the two variable version of Theorem~\ref{thm:greedyk} are as follows. \begin{Lemma} \label{lemma:f} Let $n$ and $m$ be integers, $n \geq 1$ and $0 \leq m \leq \binom{n}{2}$, and define $k$ by \begin{equation*} k = \max \{ i~|~\mbox{$i$ is an integer on $[0,n]$ such that $f(i) \leq m$} \}. \end{equation*} Then the quantity $k$ is well defined, and \begin{equation*} k = \left\lfloor n + \half - \sqrt{ n^2 - n - 2m + \frac{9}{4} } \right\rfloor. \end{equation*} \end{Lemma} % see save.tex for proof \begin{Lemma} \label{lemma:g} Let $n$ and $m$ be integers, $n \geq 1$ and $1 \leq m \leq \binom{n}{2}$, and define $k$ by \begin{equation*} k = \max \{ i~|~ \mbox{$i$ is a positive integer such that $g(i) \leq m$} \}. \end{equation*} Then the quantity $k$ is well defined, and \begin{equation*} k = \left\lfloor \frac{3}{4} + \sqrt{ \frac{m}{2}-\frac{7}{16} } \right\rfloor. % \leq \frac{n}{2}. \end{equation*} \end{Lemma} % see save.tex for proof \begin{Corollary} \label{cor:greedyedges} Let $G$ be a graph with $n$ vertices and $m$ edges. Then \begin{equation*} \greedynum(G) \geq \left\{ \begin{array}{ll} \left\lfloor n + \half - \sqrt{n^2 - n - 2m + \frac{9}{4}} \right\rfloor \quad & \mbox{if}~m \leq \frac{8 n^2 - 14 n + 28}{25}, \\ \left\lfloor \frac{3}{4} + \sqrt{ \frac{m}{2} - \frac{7}{16} } \right\rfloor \quad & \mbox{if}~m \geq \frac{8 n^2 - 14 n + 28}{25}. \\ \end{array} \right. \end{equation*} \end{Corollary} \begin{myproof} The case $m = 0$ can be taken care of by a short analysis that we will omit. So, let $G$ be a graph with $n \geq 2$ vertices and $m \geq 1$ edges. Some arithmetic yields \begin{equation*} f \left( \frac{2n+2}{5} \right) = g \left( \frac{2n+2}{5} \right) = \frac{8 n^2 - 14 n + 28}{25}. \end{equation*} Now we consider two cases. \emph{Case 1.} Suppose that $m \leq \frac{8 n^2 - 14 n + 28}{25} = f \big( \frac{2n+2}{5} \big)$. Define $k$ by \begin{equation*} k = \max \{ i~|~\mbox{$i$ is an integer in $[0,n]$ such that $f(i) \leq m$} \}. \end{equation*} We have $f(k) \leq m \leq f \big( \frac{2n+2}{5} \big)$. Since $f(i)$ is an increasing function on $[0,n]$, it follows that $k \leq \frac{2n+2}{5}$. Therefore, $\greedynum(G) \geq k$, by Theorem~\ref{thm:greedyk}. Also, by Lemma~\ref{lemma:f}, \begin{equation*} k = \left\lfloor n + \half - \sqrt{ n^2 - n - 2m + \frac{9}{4} } \right\rfloor. \end{equation*} \emph{Case 2.} Suppose that $m \geq \frac{8 n^2 - 14 n + 28}{25} = g \big( \frac{2n+2}{5} \big)$. Define $k$ by \begin{equation} k = \max \{ i~|~ \mbox{$i$ is a positive integer such that $g(i) \leq m$} \}. \end{equation} By Lemma~\ref{lemma:g}, \begin{equation} \label{eq:gcase} k = \left\lfloor \frac{3}{4} + \sqrt{ \frac{m}{2}-\frac{7}{16} } \right\rfloor. % \leq \frac{n}{2}. \end{equation} If $k \geq \frac{2n+2}{5}$, then we have the desired conclusion $\greedynum(G) \geq k$, by Theorem~\ref{thm:greedyk} and the fact that $m \geq g(k)$. If $k \leq \frac{2n+2}{5}$, then since $f$ is increasing in $[-\infty,n]$, we have \begin{equation*} m \geq g \left( \frac{2n+2}{5} \right) = f \left( \frac{2n+2}{5} \right) \geq f(k). \end{equation*} By the case $k \leq \frac{2n+2}{5}$ in Theorem~\ref{thm:greedyk}, $\greedynum(G) \geq k$. \end{myproof} Corollary~\ref{cor:greedyedges} is sometimes more convenient in the following form. \begin{Corollary} \label{cor:greedyedgesmin} Let $G$ be a graph with $n$ vertices and $m \geq 1$ edges. Then \begin{equation*} \greedynum(G) \geq \min ( \left\lfloor n + \half - \sqrt{n^2 - n - 2m + \frac{9}{4}} \right\rfloor , \left\lfloor \frac{3}{4} + \sqrt{ \frac{m}{2} - \frac{7}{16} } \right\rfloor ). \end{equation*} \end{Corollary} \begin{myproof} Let $G$, $n$ and $m$ be as above. The following two implications can be shown: \begin{align*} n + \half - \sqrt{n^2 - n - 2m + \frac{9}{4}} & \leq \frac{3}{4} + \sqrt{ \frac{m}{2} - \frac{7}{16} } \quad & \Rightarrow \quad m & \leq \frac{8 n^2 - 14 n + 28}{25}, \\ n + \half - \sqrt{n^2 - n - 2m + \frac{9}{4}} & \geq \frac{3}{4} + \sqrt{ \frac{m}{2} - \frac{7}{16} } \quad & \Rightarrow \quad m & \geq \frac{8 n^2 - 14 n + 28}{25}. \end{align*} (The details are omitted). The conclusion follows from Corollary~\ref{cor:greedyedges}. \end{myproof} \section{The Hybrid Approach} \label{sec:hybrid} The $\pO(m \sqrt n)$ time general matching algorithms of Micali and Vazirani~\cite{MicaliVazirani, PetersonLoui88} and Blum~\cite{Blum:ICALP90} operate in phases. Each phase uses $\pO(m)$ time, and there are at most $2 \sqrt{\matchnum}$ phases. A matching $M$ is maintained; initially, $M$ has size, say, $\alpha$, $0 \leq \alpha \leq \matchnum$. Each phase except the last enlarges $M$, so there are at most $\matchnum - \alpha + 1$ phases. A bound on the running time $T_g$ of these general matching algorithms, therefore, is \begin{equation} \label{eq:hybridbasic} T_g = \pO ( m \cdot \min( 2 \sqrt { \matchnum } , \matchnum - \alpha ) ). \end{equation} (This bound and others in this section are actually too low by a $\pO(m)$ term. For simplicity this is ignored in the remainder of this section.) Now consider a hybrid algorithm that finds an initial matching in $\pO(m+n)$ time using the greedy procedure, and then uses one of the $\pO(m \sqrt n)$ general matching algorithms. By Corollary~\ref{cor:greedyedgesmin}, we have \begin{equation} \alpha \geq \greedynum \geq \min ( \left\lfloor n + 1/2 - \sqrt{n^2 - n - 2m + 9/4 } \right\rfloor , \left\lfloor 3/4 + \sqrt{ m/2 - 7/16 } \right\rfloor ). \end{equation} Substituting into~\eqref{eq:hybridbasic} yields a bound on the running time $T_h$ of a hybrid algorithm: \begin{equation} \label{eq:hybridone} T_h = \pO ( m \cdot \min( 2 \sqrt { \matchnum }, \matchnum - \min ( n - \sqrt{n^2 - n - 2m } , \sqrt{ m/2 } ) ) ). \end{equation} This bound is tighter than $\pO(m \sqrt{\matchnum})$ for graphs that are dense relative to $\matchnum$. Let us see what happens when~\eqref{eq:hybridone} is used to obtain a bound that is in terms of only $n$ and $m$. Substituting $\matchnum \leq n/2$ yields \begin{equation*} T_h = \pO ( m \cdot \min( 2 \sqrt { n/2 }, n/2 - \min ( n - \sqrt{n^2 - n - 2m } , \sqrt{ m/2 } ) ) ). \end{equation*} The $n - \sqrt{n^2 - n - 2m }$ term turns out to be redundant; eliminating it gives \begin{equation} \label{eq:hybridtwo} T_h = \pO ( m \cdot \min( 2 \sqrt { n/2 }, n/2 - \sqrt{ m/2 } ) ). %T_h = \pO ( m \cdot \min( \sqrt { n }, \frac{n - \sqrt{2 m}}{2 \sqrt{2}}) ). \end{equation} The right side of~\eqref{eq:hybridtwo} reduces to $\pO(m \sqrt n)$ unless $m$ is $\Theta( \binom{n}{2} )$; thus~\eqref{eq:hybridtwo} is almost no improvement over $\pO(m \sqrt{n})$. In practice, however, it might be useful to bound the number of phases by using the non-asymptotic version of~\eqref{eq:hybridtwo}. The bounds~\eqref{eq:hybridone} and~\eqref{eq:hybridtwo} imply a complementary relationship between the greedy procedure and general matching algorithms that use repeated $\pO(m)$ time augmentation phases. For dense graphs, the greedy procedure finds a large matching, and few augmentation phases are needed; for sparse graphs, each augmentation phase is fast. Although hybrid algorithms has long been considered to give better performance than, say, using Micali and Vazirani's algorithm alone~\cite{MoretShapiro}, this specific complementary relationship seems not to have been generally known. Since the $\pO(m \sqrt{n})$ general matching algorithms are complicated~\cite{PetersonLoui88}, a less complicated but possibly slower algorithm is sometimes preferred. For example, one might do just one augmentation per phase~\cite{MoretShapiro}. This can require as many as $n/2$ augmenting phases, as opposed to $\pO(\sqrt{n})$ phases. In this case the greedy procedure's performance bounds take on a larger role. An analysis similar to the one earlier in this section shows that the running time for the resulting hybrid algorithm is \begin{equation} \pO(m \cdot \max (\sqrt{n^2 - n - 2 m} - n/2, n/2 - \sqrt{m/2} )). \end{equation} For dense graphs this is a significant improvement over $\pO(m n)$. \section{Acknowledgement} The author thanks M. Krishnamoorthy and the anonymous referees for valuable comments. \begin{thebibliography}{10} \bibitem{ABMP} H.~Alt, N.~Blum, K.~Mehlhorn, and M.~Paul. \newblock Computing a maximum cardinality matching in a bipartite graph in time $\textup{O} ( n^{1.5} \sqrt{m / \log n} )$. \newblock {\em Information Processing Letters}, 37:237--240, February 1991. \bibitem{Berge} Claude Berge. \newblock {\em Graphs and Hypergraphs}. \newblock North-Holland Publishing Company, 1973. \bibitem{Blum:ICALP90} Norbert Blum. \newblock A new approach to maximum matching in general graphs. \newblock In {\em {ICALP} 90 Automata, Languages and Programming}, pages 586--597, Berlin, July 1990. Springer. \bibitem{ErdosGallai1959} Paul Erd{\"{o}}s and T.~Gallai. \newblock On maximal paths and circuits of graphs. \newblock {\em Acta Math. Acad. Sc. Hungar.}, 10:337--356, 1959. \bibitem{FederMotwani:stoc91} Tom{\'a}s Feder and Rajeev Motwani. \newblock Clique partitions, graph compression, and speeding-up algorithms. \newblock In Baruch Awerbuch, editor, {\em Proceedings of the 23rd Annual {ACM} Symposium on the Theory of Computing}, pages 123--133, New Orleans, LA, May 1991. ACM Press. \bibitem{Galil} Zvi Galil. \newblock Efficient algorithms for finding maximum matchings in graphs. \newblock {\em Computing Surveys}, 18:23--38, 1986. \bibitem{HK} John~E. Hopcroft and Richard~M. Karp. \newblock An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs. \newblock {\em SIAM Journal on Computing}, 2(4), December 1973. \bibitem{LovaszPlummer} L.~Lov{\'{a}}sz and M.~D. Plummer. \newblock {\em Matching Theory}, volume 121 of {\em North-Holland mathematics studies}. \newblock North-Holland, Amsterdam, 1986. \bibitem{MicaliVazirani} S.~Micali and V.~V. Vazirani. \newblock An $\textup{O} ( \bibsqr{ \left| V \right| } \cdot \left| {E} \right| )$ algorithm for finding maximal matching in general graphs. \newblock In {\em Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science}, pages 17--27. IEEE Computer Society Press, 1980. \bibitem{MoretShapiro} B.~M.~E. Moret and H.~D. Shapiro. \newblock {\em Algorithms from P to NP}. \newblock The Benjamin/Cummings Publishing Company, Inc., 1991. \bibitem{PapaSteig} Christos~H. Papadimitriou and Kenneth Steiglitz. \newblock {\em Combinatorial optimization: algorithms and complexity}. \newblock Prentice Hall, 1982. \bibitem{PetersonLoui88} Paul~A. Peterson and Michael~C. Loui. \newblock The general maximum matching algorithm of {M}icali and {V}azirani. \newblock {\em Algorithmica}, 3:511--533, 1988. \bibitem{ShapiraGreedyMatchingC} Andrew Shapira. \newblock Classes of graphs for which an $\textup{O} ({m}+{n})$ time greedy matching procedure does and does not find a maximum matching, in preparation. \bibitem{ShapiraGreedyMatchingA} Andrew Shapira. \newblock Matchings, degrees, and $\textup{O} ({m}+{n})$ time procedures, in preparation. \end{thebibliography} \end{document}