Choosing the Efficient Algorithm for Vertex Cover Problem

Abstract

The vertex cover (VC) problem belongs to the class of NP-complete graph theoretical problems, which plays a central role in theoretical computer science and it has a numerous real life applications. We are unlikely to find a polynomial-time algorithm for solving vertex-cover problem exactly. Vertex-cover exhibits a coverable–uncoverable phase transition. The relationship of vertex-cover with other NP-complete problems is thoroughly studied in this work. This thesis work also analyzes the various algorithms on minimum vertex cover for standard classes of random graphs. The performance of all algorithms is compared with the complexity and the output solution that of the branch-and-bound problem solver (BB), approximation algorithm, greedy algorithm, simple genetic algorithm (GA), primal-dual based algorithm (PDB) and the alom’s algorithm. The results indicate that all algorithms give near optimal solutions. The performance differences of all algorithms on a graph are relatively small to obtain a vertex-cover. For undirected graphs, better performance is achieved by alom’s algorithm and for weighted graphs, better performance is achieved by primal-dual based approach. Additionally, alom’s algorithm is extended in order to give the all possible vertex-covers of a graph and the algorithm is implemented in c++.