New approximation results on graph matching and related problems

For a graph G with e edges and n vertices, a maximum cardinality matching of G is a maximum subset M of edges such that no two edges of M are incident at a common vertex. The best known algorithm for solving the problem in general graphs requires O(n5/2) time. We first propose an approximate maximum cardinality matching algorithm that runs in O(e+n) sequential time yielding a matching of size at least e/n−1, improving the bound known before. For bipartite graphs, the algorithm yields a matching of size at least 2e/n. The proposed algorithms are extremely simple, and the derived lowerbounds are existentially tight. Next, the proposed maximum cardinality matching algorithm is extended to the weighted case running in O(e+n) time. The problem of approximate maximum matching has a number of applications, for example in, Vertex Cover, TSP, MAXCUT, and VLSI physical design problems.