An Effective Algorithm for Minimum Weighted Vertex Cover Problem

Authors: S. Balaji, V. Swaminathan, K. Kannan

Abstract:

The Minimum Weighted Vertex Cover (MWVC) problem is a classic graph optimization NP - complete problem. Given an undirected graph G = (V, E) and weighting function defined on the vertex set, the minimum weighted vertex cover problem is to find a vertex set S V whose total weight is minimum subject to every edge of G has at least one end point in S. In this paper an effective algorithm, called Support Ratio Algorithm (SRA), is designed to find the minimum weighted vertex cover of a graph. Computational experiments are designed and conducted to study the performance of our proposed algorithm. Extensive simulation results show that the SRA can yield better solutions than other existing algorithms found in the literature for solving the minimum vertex cover problem.

Keywords: Weighted vertex cover, vertex support, approximation algorithms, NP-complete problem.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1076814

References:

[1] Bollobas. B : Random graphs (2nd Ed.). Cambridge, UK: Cambridge University press, 2001.
[2] Berman. P and Fujito. T: On approximation properties of the independent set problem for low degree graphs, Theory of Computing Syst., vol. 32, pp. 115 - 132, 1999.
[3] Cormen. T. H, C. E. Leiserson, R. L. R., and Stein. C: Introduction to algorithms, 2nd ed., McGraw - Hill, New York , 2001.
[4] Dehne. F, et al.: Solving large FPT problems on coarse grained parallel machines, Available: http://www.scs.carleton.ca/fpt/papers/index.htm.
[5] Fellows. M. R: On the complexity of vertex cover problems, Technical report, Computer science department, University of New Mexico, 1988.
[6] Garey. M. R, Johnson. D. S: Computers and Intractability: A Guide to the theory NP - completeness. San Francisco: Freeman ,1979.
[7] Garey. M. R, Johnson. D. S, and Stock Meyer. L: Some simplified NP - complete graph problems, Theoretical computer science, Vol.1563, pp. 561 - 570, 1999.
[8] Glover. F: Tabu Search - Part I, ORSA journal of computing, vol. 1, No.3, (1989), pp. 190 - 206.
[9] Glover. F: Tabu search: A Tutorial, Interface 20, pp. 74 - 94, 1990.
[10] Gomes. F. C, Meneses. C. N, Pardalos. P. M and Viana. G. V. R: Experimental analysis of approximation algorithms for the vertex cover and set covering problems, Journal of computers and Operations Research, vol. 33, pp. 3520 - 3534, 2006.
[11] Hastad. J: Some Optimal Inapproximability Results., Journal of the ACM, vol. 48, No.4, pp. 798 - 859, 2001.
[12] Hochbaum. D. S: Approximation algorithm for the set covering and vertex cover problems, SIAM Journal on computing, 11(3), 555 - 6, 1982.
[13] Karp. R. M: Reducibility among combinatorial problems, Plenum Press, New York, pp. 85 - 103, 1972.
[14] Likas, A and Stafylopatis, A: A parallel algorithm for the minimum weighted vertex cover problem, Information Processing Letters, vol. 53, pp. 229 - 234, 1995.
[15] Motwani. R: Lecture Notes on Approximation Algorithms, Technical Report, STAN-CS-92-1435, Department of Computer Science, Stanford University, 1992.
[16] Neidermeier. R and Rossmanith. P: On efficient fixed-parameter algorithms for weighted vertex cover, Journal of Algorithms, vol. 47, pp. 63 - 77, 2003.
[17] Pitt. L: A Simple Probabilistic Approximation Algorithm for Vertex Cover, Technical Report, YaleU/DCS/TR-404, Department of Computer Science, Yale University, 1985.
[18] Monien. B and Speckenmeyer. E: Ramsey numbers and an approximation algorithm for the vertex cover problems, Acta Informatica, vol. 22, pp. 115 - 123, 1985.
[19] Shyu. S.J, Yin. P.Y and Lin. B.M.T: An ant colony optimization algorithm for the minimum weight vertex cover problem, Annals of Operations Research, Vol. 131, pp. 283 - 304, 2004.
[20] Weight. M and Hartmann. A. K: The number of guards needed by a museum - a phase transition in vertex covering of random graphs., Phys - Rev. Lett., 84, 6118, 2000b.
[21] Weight. M and Hartmann. A. K.: Minimal vertex covers on finiteconnectivity random graphs - A hard-sphere lattice-gas picture, Phys. Rev. E, 63, 056127.