evelyn6666/Comparison_between_two_ways_to_solve_MIN_VERTEX_COVER

Vertex cover of a graph is a set of vertexes such that each edges of the graph is incident to at least one vertex of the set. In this project, we use three different algorithms (CNF-SAT-VC, APPROXVC-1, and APPROX-VC-2) that solving the vertex cover problem. The algorithm CNF-SAT-VC create a polynomial reduction of the decision version of VERTEX COVER to CNF-SAT. Then we add other two additional ways to solve MIN-VERTEX-COVER, APPROX-VC-1 and APPROXVC-2 respectively. APPR1 just picks a vertex of highest degree and add it to the vertex cover, meanwhile, throw away all edges incident on that vertex and repeat till no edges remain. APPR2 is an algorithm which pick an edge randomly and delete all edges which attach to the previous picked one until no edges left.

C++