An Effective Algorithm for Minimum Weighted Vertex Cover Problem

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.

• S. Balaji
• V. Swaminathan
• K. Kannan

• Weighted vertex cover
• vertex support
• approximation algorithms
• NP-complete problem.

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