Issue: 2015/Vol.25/No.4, Pages 5-18
A NEW AND FAST APPROXIMATION ALGORITHM FOR VERTEX COVER USING A MAXIMUM INDEPENDENT SET (VCUMI)
Imran Khan
, Naveed Riaz
Cite as: I. Khan, N. Riaz. A new and fast approximation algorithm for vertex cover using a maximum independent set (VCUMI). Operations Research and Decisions 2015: 25(4), 5-18. DOI 10.5277/ord150401
Abstract
The importance of non-deterministic polynomial (NP) problems in real world scenarios has compelled researchers to consider simple ways of finding approximate solutions to these problems in polynomial time. Minimum vertex cover is an NP complete problem, where the objective is to cover all the edges in a graph with the minimal number of vertices possible. The maximal independent set and maximal clique problems also belong to the same class. An important property that we have ana- lyzed while considering various approaches to find approximate solutions to the minimum vertex cover problem (MVC) is that solving MVC directly can result in a bigger error ratio. We propose a new approximation algorithm for the minimum vertex cover problem called vertex cover using a maximum independent set (VCUMI). This algorithm works by removing the nodes of a maximum independent set until the graph is an approximate solution of MVC. Based on empirical results, it can be stated that VCUMI outperforms all competing algorithms presented in the literature. Based on all the benchmarks used, VCUMI achieved the worst case error ratio of 1.033, while VSA, MDG and NOVAC-1 gave the worst error ratios of 1.583, 1.107 and 1.04, respectively.
Keywords: non-deterministic polynomial, vertex cover, independent set, benchmark, error ratio
Received: 23 December 2014 Accepted: 30 November 2015