A tight analysis of the maximal matching heuristic

We study the algorithm that iteratively removes adjacent vertices from a sim-ple, undirected graph until no edge remains. This algorithm is a well-known 2-approximation to three classical NP-hard optimization problems: MINIMUM VERTEX COVER,M INIMUM MAXIMAL MATCHING and MINIMUM EDGE DOMINATING SET. We show that the worst-case approximation factor of this simple method can be expressed in a finer way when assumptions on the density of the graph is made. For graphs with anaverage degree at least ffln, called weakly ffl-dense graphs, we show that the asymptotic approximation factor is min{2, 1/(1- p1- ffl)}. For graphs with a minimum degree atleast ffln- strongly ffl-dense graphs- we show that the asymptotic approximation factor is min{2, 1/ffl}. These bounds are obtained through a careful analysis of the tight examples