A ($2-\varepsilon$)-approximation ratio for vertex cover problem on special graphs

Subject Areas : Combinatorics, Graph theory

N. Yekezare ¹ , M. Zohrehbandian ² , M. Maghasedi ³

1 - Department of Mathematics, Karaj Branch, Islamic Azad University, Karaj, Iran
2 - Department of Mathematics, Karaj Branch, Islamic Azad University, Karaj, Iran
3 - Department of Mathematics, Karaj Branch, Islamic Azad University, Karaj, Iran

Received: 2023-05-01 Accepted : 2023-06-30 Published : 2023-06-01

Keywords: Discrete optimization, Vertex cover problem, Complexity theory,

Abstract :

‎The vertex cover problem is a famous combinatorial problem‎, ‎and its complexity has been heavily studied‎. ‎It is known that it is hard to approximate to within any constant factor better than $2$‎, ‎while a $2$-approximation for it can be trivially obtained‎. ‎In this paper‎, ‎new properties and new techniques are introduced which lead to approximation ratios smaller than $2$ on special graphs;‎ ‎e.g‎. ‎graphs for which their maximum cut values are less than $0.999|E|$‎. ‎In fact‎, ‎we produce a ($1.9997$)-approximation ratio on graph $G$‎, ‎where the ($0.878$)-approximation algorithm of the Goemans-Williamson for the maximum cut problem on $G$ produces a value smaller than $0.877122|E|$‎.

References:

[1] D. Avis, T. Imamura, A list heuristic for vertex cover, Oper. Res. Lett. 35 (2007), 201-204.

[2] H. Bhasin, Harnessing genetic algorithm for vertex cover problem, Inter. J. Comput. Sci. Engin. 4 (2012), 218-223.

[3] V. Chvatal, A greedy heuristic for the set covering problem, Math. Oper. Res. 4 (3) (1979), 233-235.

[4] F. Delbot, C. Andlaforest, A better list heuristic for vertex cover, Inform. Proc. Lett. 107 (2008), 125-127.

[5] F. Delbot, C. Laforest, Analytical and experimental comparison of six algorithms for the vertex cover problem, ACM J. Experimental Algorithmics. 15 (2010), 1-26.

[6] I. Dinur, S. Safra, On the hardness of approximating minimum vertex cover, Annal. Math. 162 (2005), 439-485.

[7] M. Fayaz, S. Arshad, A. S. Shah, A. Shah, Approximate methods for minimum vertex cover fail to provide optimal results on small graph instances: A review, Inter. J. Control. Automation. 11 (2) (2018), 135-150.

[8] M. R. Garey, D. Andjohnson, Computers and Intractability, Freeman, New York, 1979.

[9] M. X. Goemans, D.P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM. 42 (6) (1995), 1115-1145.

[10] R. Jovanovic, M. Tuba, An ant colony optimization algorithm with improved pheromone correction strategy for the minimum weight vertex cover problem, Appl. Soft. Comput. 11 (2011), 5360-5366.

[11] S. Khot, On the Power of Unique 2-Prover 1-Round Games, Proceeding of 34th ACM Symposium on Theory of Computing, STOC, 2002.

[12] S. Khot, O. Regev, Vertex cover might be hard to approximate to within 2−ε, J. Computer. System. Sciences. 74 (2008), 335-349.

[13] C. Savage, Depth-first search and the vertex cover problem, Inform. Proc. Lett. 14 (1982), 233-235.

[14] S. J. Shyu, P. Y. Yin, B. M. T. Lin, An ant colony optimization algorithm for the minimum weight vertex cover problem, Annal. Oper. Res. 131 (2004), 283-304.

[15] A. Singh, A. K. Gupta, A hybrid heuristic for the minimum weight vertex cover problem, Asia-Pacific J. Oper. Res. 23 (2006), 273-285.

[16] S. Voβ, A. Fink, A hybridized tabu search approach for the minimum weight vertex cover problem, J. Heuristics. 18 (2012), 869-876.

[17] C. Witt, Analysis of an iterated local search algorithm for vertex cover in sparse random graphs, Theore. Comput. Sci. 425 (2012), 117-125.

[18] X. Xu, J. Ma, An efficient simulated annealing algorithm for the minimum vertex cover problem, Neurocomputing. 69 (2006), 913-916.