On hard instances of approximate vertex cover

ABSTRACT

We show that if there is a 2 − &epsis; approximation algorithm for vertex cover on graphs with vector chromatic number at most 2 + δ, then there is a 2 − f(&epsis;, δ) approximation algorithm for vertex cover for all graphs.

REFERENCES

• 1: Bar-Yehuda, R., and Even, S. 1985. A local-ratio theorem for approximating the weighted vertex cover problem. Ann. Disc. Math. 25, 27--45.
• 2: Avrim Blum, New approximation algorithms for graph coloring, Journal of the ACM (JACM), v.41 n.3, p.470-516, May 1994 [doi>10.1145/176584.176586]
• 3: Avrim Blum , David Karger, An Õ(n3/14)-coloring algorithm for 3-colorable graphs, Information Processing Letters, v.61 n.1, p.49-53, Jan. 14, 1997 [doi>10.1016/S0020-0190(96)00190-1]
• 4: Moses Charikar, On semidefinite programming relaxations for graph coloring and vertex cover, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.616-620, January 06-08, 2002, San Francisco, California
• 5: Dinur, I., and Safra, S. 2005. On the hardness of approximating minimum vertex cover. Ann. Math. 162, 1.
• 6: Uriel Feige , Michael Langberg , Gideon Schechtman, Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.283-292, November 16-19, 2002
• 7: Michel X. Goemans , David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), v.42 n.6, p.1115-1145, Nov. 1995 [doi>10.1145/227683.227684]
• 8: Grotschel, M., Lóvasz, L., and Schrijver, A. 1981. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 2, 169--197.
• 9: Eran Halperin, Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs, SIAM Journal on Computing, v.31 n.5, p.1608-1623, 2002 [doi>10.1137/S0097539700381097]
• 10: Karakostas, G. 2005. A better approximation ratio for the vertex cover problem. In Proceedings of the 32nd International Conference on Automata Languages and Programming. ACM, New York, 1043--1050.
• 11: D. Karger , R. Motwani , M. Sudan, Approximate graph coloring by semidefinite programming, Proceedings of the Proceedings 35th Annual Symposium on Foundations of Computer Science, p.2-13, November 20-22, 1994 [doi>10.1109/SFCS.1994.365710]
• 12: Khot, S., and Regev, O. 2003. Vertex cover might be hard to approximate to within 2 − &epsis;. In Proceedings of the 18th Annual IEEE Conference on Computational Complexity. IEEE Computer Society Press, Los Alamitos, CA, 379--386.
• 13: Jon Kleinberg , Michel X. Goemans, The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover, SIAM Journal on Discrete Mathematics, v.11 n.2, p.196-204, May 1998 [doi>10.1137/S0895480195287541]
• 14: L. Lovasz, Matching Theory (North-Holland mathematics studies), Elsevier Science Ltd, 1986
• 15: Burkhard Monien , Ewald Speckenmeyer, Ramsey numbers and an approximation algorithm for the vertex cover problem, Acta Informatica, v.22 n.1, p.115-123, April 1985 [doi>10.1007/BF00290149]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory

Keywords:
Approximation algorithms, vertex cover