Using a maximum matching to find a minimum vertex cover in a graph

The Minimum Vertex Cover Problem (VCP) is to find a smallest set of vertices in a graph such that every edge has at least one vertex in the set. The Maximum Matching Problem (MP) is to find a largest set of edges in a graph such that no vertex belongs to more than one edge in the set. The MP is related to the VCP in that the cardinality of a maximum matching provides a lower bound on the cardinality of a vertex cover because any vertex cover must include at least one vertex from each edge in the matching. Also, the MP is polynomial solvable whereas the VCP is NP-complete. In this dissertation, a maximum matching is used as a heuristic to find a minimum vertex cover in a graph. Specifically, two approximation algorithms are introduced for solving the VCP. These algorithms have a worst-case ratio strictly smaller 2 than and are based on Edmonds' Algorithm and our Coloring Algorithm for finding a maximum matching in a graph.; The proposed vertex cover algorithms were compared computationally with three other algorithms available in the literature. Three main types of test cases were used in the experiment: standard test cases, each with a known optimal solution; randomly-generated test cases, with the densities of edges controlled; and a group of test cases derived from a real-world application. The computational results indicate that, in general, the proposed algorithms perform well across all of the test cases in that solutions are reasonably good (at least not far from to the best one) compared to the other test algorithms. The proposed algorithms also provide a bound on the optimal solution, which is not available in the other algorithms. Another advantage is that the proposed algorithms can identify graphs in which the cardinality of a maximum matching is equal to the cardinality of a minimum vertex cover.