A new and fast approximation algorithm for vertex cover using a maximum independent set (VCUMI)

• Autorzy: Khan I. , Riaz N.

Identyfikatory

DOI

10.5277/ord150401

• Języki publikacji: EN

Abstrakty

EN

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 analyzed 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.

Słowa kluczowe

EN

non-deterministic polynomial; vertex cover; independent set; benchmark; error ratio

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Operations Research and Decisions
• Rocznik: 2015
• Tom: Vol. 25, No. 4
• Strony: 5--18
• Opis fizyczny: bibliogr. 24 poz., rys., tab.

Twórcy

autor

Khan I.

• Department of Computer Science, University of Swat, Pakistan

autor

Riaz N.

• College of Computer Science and IT, University of Dammam, Saudi Arabia

Bibliografia

• [1] ASGEIRSSON E.I., STEIN C., Divide-and-conquer approximation algorithm for vertex cover, SIAM Journal on Discrete Mathematics, 2009, 23 (3), 1261.
• [2] BALAJI S., SWAMINATHAN V., KANNAN K., Optimization of unweighted minimum vertex cover, World Academy of Science, Engineering and Technology, 2010, 43, 716.
• [3] CHEN J., HUANG X., KANJ I.A., XIA G., Linear FPT reductions and computational lower bounds, Proc. 36th Annual ACM Symposium on Theory of Computing, ACM, 2004, 212.
• [4] CHVATAL V., A greedy heuristic for the set-covering problem, Mathematics of Operations Research, 1979, 4 (3), 233.
• [5] CLARKSON K.L., A modification of the greedy algorithm for vertex cover, Information Processing Letters, 1983, 16 (1), 23.
• [6] CORMEN T.H., LEISERSON C.E., RIVEST R.L., STEIN C., Introduction to Algorithms, 2, MIT Press, Cambridge 2001.
• [7] AVIS D., IMAMURA T., A list heuristic for vertex cover, Operations Research Letters, 2007, 35 (2), 201.
• [8] DA SILVA M.O., GIMENEZ-LUGO G.A., DA SILVA M.V., Vertex cover in complex networks, Interna-tional Journal of Modern Physics C, 2013, 24 (11).
• [9] DELBOT F., LAFOREST C., A better list heuristic for vertex cover, Information Processing Letters, 2008, 107 (3), 125.
• [10] DELBOT F., LAFOREST C., Analytical and experimental comparison of six algorithms for the vertex cover problem, Journal of Experimental Algorithmics, 2010, 15, 1.
• [11] DEMAINE E.D., FOMIN F.V., HAJIAGHAYI M., THILIKOS D.M., Subexponential parameterized algo-rithms on bounded-genus graphs and h-minor-free graphs, Journal of the ACM, 2005, 52 (6), 866.
• [12] DINUR I., SAFRA S., The importance of being biased, Proc. 34th Annual ACM Symposium on Theory of Computing, ACM, 2002, 33.
• [13] DINUR I., SAFRA S., On the hardness of approximating minimum vertex cover, Annals of Mathemat-ics, 2005, 162 (1), 439.
• [14] GAREY M.R., JOHNSON D.S., Computers and Intractability. A Guide to the Theory of NP- -Completeness, W.H. Freeman & Co., New York 1979, 29.
• [15] GAJUREL S., BIELEFELD R., A simple NOVAC. Near optimal vertex cover algorithm, Procedia Com-puter Science, 2012, 9, 747.
• [16] HALLDORSSON M.M., RADHAKRISHNAN J., Greed is good: Approximating independent sets in sparse and bounded-degree graphs, Algorithmica, 1997, 18 (1), 145.
• [17] IMRAN K., HASHAM K., Modified vertex support algorithm. A new approach for approximation of mini-mum vertex cover, Research Journal of Computer and Information Technology Sciences, 2013, 1 (6), 7.
• [18] IMRAN K., ISRAR A., MUZAMMIL K., AVSA, modified vertex support algorithm for approximation of MVC, International Journal of Advanced Science and Technology, 2014, 67, 71.
• [19] KARP R.M., Reducibility among Combinatorial Problems, Springer, 1972.
• [20] LI S., WANG J., CHEN J., WANG Z., An approximation algorithm for minimum vertex cover on general graphs, The Third International Symposium on Electronic Commerce and Security Workshops, ISECS, Guangzhou, P.R. China, 2010, 249.
• [21] SANCHIS L.A., Test case construction for the vertex cover problem, Series in Discrete Mathematics and Theoretical Computer Science, DIMACS, 1994, 15, 315.
• [22] SINGH A., GUPTA A.K., A hybrid heuristic for the minimum weight vertex cover problem, Asia- -Pacific Journal of Operational Research, 2006, 23 (2), 273.
• [23] Vertex Cover Benchmark Instances, http://www.cs.hbg.psu.edu/txn131/vertex_cover.html, retrieved April 23, 2015.
• [24] XU X., MA J., An efficient simulated annealing algorithm for the minimum vertex cover problem, Neuro-Computing, 2006, 69 (7), 913.