Optimization of Unweighted Minimum Vertex Cover

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

Abstract:

The Minimum Vertex Cover (MVC) problem is a classic graph optimization NP - complete problem. In this paper a competent algorithm, called Vertex Support Algorithm (VSA), is designed to find the smallest vertex cover of a graph. The VSA is tested on a large number of random graphs and DIMACS benchmark graphs. Comparative study of this algorithm with the other existing methods has been carried out. Extensive simulation results show that the VSA can yield better solutions than other existing algorithms found in the literature for solving the minimum vertex cover problem.

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

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

References:

[1] C. Aggarwal , J. B Orlin and R. P Tai, Optimized cross cover for the independent set problem, Operations Research, Vol. 45, (1997), 226-234.
[2] P. Berman and T. Fujito, On approximation properties of the independent set problem for low degree graphs, Theory of Computing Syst., Vol. 32, (1999), 115 - 132.
[3] B. Bollobas, Random graphs, 2nd Ed., Cambridge, UK: Cambridge University press (2001).
[4] J. M. Bourjolly , P. Gill , G. Laporte and H. Mercure, An exact quadratic 0-1 algorithm for the stable set problem, American Mathematical Society Providence, RI. 1996, pp. 53-73.
[5] T. H. C. E. Cormen, R. L. R. Leiserson, and C. Stein, Introduction to algorithms, 2nd ed., McGraw - Hill, New York (2001).
[6] F. Dehne et. al, Solving large FPT problems on coarse grained parallel machines, Available: http://www.scs.carleton.ca/fpt/papers/index.htm.
[7] DIMACS clique benchmarks, Benchmark instances made available by electronic transfer at dimacs.rutgers.edu, Rutgers Univ., Piscataway. NJ. (1993).
[8] M. R. Fellows, On the complexity of vertex cover problems, Technical report, Computer science department, University of New Mexico (1988).
[9] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the theory NP - completeness, San Francisco: Freeman (1979).
[10] M. R. Garey, D. S. Johnson and L. Stock Meyer, Some simplified NP - complete graph problems, Theoretical computer science, Vol. 1563, (1999), 561 - 570.
[11] D. S. Hochbaum Efficient bounds for the stable set, vertex cover and set packing problems, Discrete Appl. Mathematics, Vol. 6, (1983), 243 - 254.
[12] R. M. Karp, Reducibility among combinatorial problems, Plenum Press, New York, (1972), pp 85 - 103.
[13] K, Katayama, A. Hamamoto and H. Narihisa, An effective local search for the maximum clique problem, Information Processing Letters, Vol. 95, (2005), 503-511.
[14] S. Khuri and T. Back, An evolutionary heuristic for the minimum vertex cover problem, J. Kunze and H. Stoyan, editors, KI - 94 workshops (Extended Abstracts), Bonn (1994), pp. 83 - 84..
[15] D. Matula, On the complete subgraph of a random graph, Combinatory mathematics and its Applications, (1970), pp. 356-369.
[16] B. Monien and E. Speckenmeyer Ramsey numbers and an approximation algorithm for the vertex cover problems, Acta Informatica, Vol. 22, (1985), 115 - 123.
[17] W. Pullan, Optimisation of unweighted/weighted maximum independent sets and minimum vertex covers, Discrete Optimization, Vol. 6, (2009), 214-219.
[18] S.J. Shyu, P.Y. Yin and B.M.T. Lin, An ant colony optimization algorithm for the minimum weight vertex cover problem, Annals of Operations Research, Vol. 131, (2004), 283 - 304.
[19] U. Stege, Resolving conflicts from problems in computational Biology, Ph.D thesis, No.13364, ETH Zurich (2000).
[20] C. Z. Tang, X. Xu et al., An algorithm based on Hopfield network learning for minimum vertex cover problem, Lecture Notes in computer science, Vol. 3173, (2004), 430 - 435,.
[21] M. Weight and A. K. Hartmann, The number of guards needed by a museum - a phase transition in vertex covering of random graphs, Phys - Rev. Lett., 84, 6118 (2000b).
[22] M. Weight and A. K. Hartmann, Minimal vertex covers on finiteconnectivity random graphs - A hard-sphere lattice-gas picture, Phys. Rev. E, 63, 056127.
[23] X. Xu and J. Ma, An efficient simulated annealing algorithm for the minimum vertex cover problem, Nerocomputing, Vol. 69, Issues 7-9, (2006), 613 - 616.