A Smart Approximation Algorithm for Minimum Vertex Cover Problem based on Min-to-Min (MtM) Strategy

In this paper, we have proposed an algorithm based on min-to-min approach. In the proposed algorithm first the degree of each vertex of the graph is calculated. Next the vertex with minimum degree is selected, after which all the neighbors of the minimum degree are located. In the neighbors of the minimum degree vertex, again the vertex with the minimum degree is found and put into the set minimum vertex cover and deleted from the graph. Again, the degree of each vertex of the updated graph is calculated and again the same process is repeated until the graph becomes empty. In case of tie, all the neighbors of the minimum degree vertices are computed and then the minimum degree vertex in all of them is added to minimum vertex degree set. The same process is repeated until the graph becomes empty. The proposed algorithm is a very simple, efficient, and easy to understand and implement. The proposed min-to-min algorithm is evaluated on small as well as on large benchmark instances and the results indicate that the performance of the min-to-min algorithm is far better as compared to the other state-of-art algorithms in term of accuracy and computation complexity. We have also used the proposed method to solve the maximum independent set problem.

@article{Haider2020,
  title     = {A Smart Approximation Algorithm for Minimum Vertex Cover Problem based on Min-to-Min (MtM) Strategy},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {11},
  number    = {12},
  year      = {2020},
  publisher = {The Science and Information Organization},
  author    = {Jawad Haider and Muhammad Fayaz},
  doi       = {10.14569/IJACSA.2020.0111232},
  url       = {https://doi.org/10.14569/IJACSA.2020.0111232}
}