An exact performance bound for an \(O(m+n)\) time greedy matching procedure (Q1378525)

Summary: We prove an exact lower bound on \(\gamma(G)\), the size of the smallest matching that a certain \(O(m+n)\) time greedy matching procedure may find for a given graph \(G\) with \(n\) vertices and \(m\) edges. The bound is precisely Erdő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 \(\gamma(G)\) is a stronger version of Erdős and Gallai's result, and so the proof of the lower bound is a new way of proving the result of Erdős and Gallai.