×

zbMATH — the first resource for mathematics

Vertex cover might be hard to approximate to within \(2 - \varepsilon \). (English) Zbl 1133.68061
Summary: Based on a conjecture regarding the power of unique 2-prover-1-round games presented in [S. Khot, “On the power of unique 2-prover 1-round games”, in: Proc. 34th ACM Symp. on Theory of Computing, STOC, May 2002, 767–775 (2002)], we show that vertex cover is hard to approximate within any constant factor better than 2. We actually show a stronger result, namely, based on the same conjecture, vertex cover on \(k\)-uniform hypergraphs is hard to approximate within any constant factor better than \(k\).

MSC:
68R10 Graph theory (including graph drawing) in computer science
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25 Approximation algorithms
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] S. Arora, B. Bollobás, L. Lovász, Proving integrality gaps without knowing the linear program, in: Proceedings of the 43rd Annual Symposium on Foundations of Computer Science, FOCS 2002, Vancouver, Canada, Nov. 2002, pp. 313-322
[2] Arora, S.; Lund, C.; Motwani, R.; Sudan, M.; Szegedy, M., Proof verification and the hardness of approximation problems, J. ACM, 45, 3, 501-555, (1998) · Zbl 1065.68570
[3] Arora, S.; Safra, S., Probabilistic checking of proofs: A new characterization of NP, J. ACM, 45, 1, 70-122, (1998) · Zbl 0903.68076
[4] Bellare, M.; Goldreich, O.; Sudan, M., Free bits, PCPs, and nonapproximability—towards tight results, SIAM J. comput., 27, 3, 804-915, (1998) · Zbl 0912.68041
[5] M. Charikar, K. Makarychev, Y. Makarychev, Near-optimal algorithms for unique games, in: Proceedings of the 38th ACM Symposium on Theory of Computing, STOC 2006 · Zbl 1301.68267
[6] S. Chawla, R. Krauthgamer, R. Kumar, Y. Rabani, D. Sivakumar, On the hardness of approximating sparsest cut and multicut, in: Proc. of 20th IEEE Annual Conference on Computational Complexity, CCC 2005, pp. 144-153 · Zbl 1132.68418
[7] I. Dinur, V. Guruswami, S. Khot, Vertex cover on k-uniform hypergraphs is hard to approximate within factor (k−3−&z.epsiv;), in: Electronic Colloquium on Computational Complexity, Technical Report TR02-027, 2002
[8] Dinur, I.; Guruswami, V.; Khot, S.; Regev, O., A new multilayered PCP and the hardness of hypergraph vertex cover, SIAM J. comput., 34, 5, 1129-1146, (2005) · Zbl 1079.68039
[9] I. Dinur, E. Mossel, O. Regev, Conditional hardness for approximate coloring, in: Proc. 38th ACM Symp. on Theory of Computing, STOC 2006 · Zbl 1301.68143
[10] Dinur, I.; Safra, S., On the hardness of approximating minimum vertex cover, Ann. of math., 162, 1, (2005), preliminary version in STOC 2002 · Zbl 1084.68051
[11] U. Feige, S. Goldwasser, L. Lovász, S. Safra, M. Szegedy, Approximating clique is almost NP-complete, in: Proc. 32nd IEEE Symp. on Foundations of Computer Science, FOCS 1991, pp. 2-12
[12] Friedgut, E., Boolean functions with low average sensitivity depend on few coordinates, Combinatorica, 18, 1, 27-35, (1998) · Zbl 0909.06008
[13] O. Goldreich, Using the FGLSS-reduction to prove inapproximability results for minimum vertex cover in hypergraphs, ECCC Technical Report TR01-102, 2001 · Zbl 1343.68094
[14] A. Gupta, K. Talwar, Approximating unique games, in: Proceedings of Annual Symposium on Discrete Algorithms, SODA 2006, pp. 99-106 · Zbl 1192.91012
[15] Guruswami, V.; Håstad, J.; Sudan, M., Hardness of approximate hypergraph coloring, SIAM J. comput., 31, 6, 1663-1686, (2002) · Zbl 1008.68052
[16] Halperin, E., Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs, SIAM J. comput., 31, 5, 1608-1623, (2002) · Zbl 1041.68130
[17] Håstad, J., Clique is hard to approximate within \(n^{1 - \operatorname{\&z.epsiv;}}\), Acta math., 182, 1, 105-142, (1999) · Zbl 0989.68060
[18] Håstad, J., Some optimal inapproximability results, J. ACM, 48, 4, 798-859, (2001) · Zbl 1127.68405
[19] J. Holmerin, Improved inapproximability results for vertex cover on k-regular hyper-graphs, in: International Colloquium on Automata, Languages, and Programming, ICALP 2002, pp. 1005-1016 · Zbl 1057.68079
[20] J. Holmerin, Vertex cover on 4-regular hyper-graphs is hard to approximate within \(2 - \operatorname{\&z.epsiv;}\), in: Proc. 34th ACM Symp. on Theory of Computing, STOC 2002, pp. 544-552 · Zbl 1192.68323
[21] G. Karakostas, A better approximation ratio for the vertex cover problem, in: Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP, Lisboa, Portugal, July 2005, pp. 1043-1050 · Zbl 1085.68112
[22] S. Khot, On the power of unique 2-Prover 1-Round games, in: Proc. 34th ACM Symp. on Theory of Computing, STOC, May 2002, pp. 767-775 · Zbl 1192.68367
[23] S. Khot, G. Kindler, E. Mossel, R. O’Donnell, Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?, in: Proc. 45th IEEE Symp. on Foundations of Computer Science, FOCS 2004, pp. 146-154 · Zbl 1135.68019
[24] S. Khot, N. Vishnoi, The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into \(\ell_1\), in: Proc. 46th IEEE Symp. on Foundations of Computer Science, FOCS 2005, pp. 53-62 · Zbl 1321.68316
[25] Margulis, G., Probabilistic characteristics of graphs with large connectivity, Prob. peredachi inform., 10, 101-108, (1974) · Zbl 0322.05147
[26] E. Mossel, R. O’Donnell, K. Oleszkiewicz, Noise stability of functions with low influences, invariance and optimality, in: Proc. 46th IEEE Symp. on Foundations of Computer Science, FOCS 2005, pp. 21-30
[27] Raz, R., A parallel repetition theorem, SIAM J. comput., 27, 3, 763-803, (1998) · Zbl 0911.68082
[28] Russo, L., An approximate zero-one law, Z. wahrsch. verw. gebiete, 61, 1, 129-139, (1982) · Zbl 0501.60043
[29] L. Trevisan, Non-approximability results for optimization problems on bounded degree instances, in: Proc. 33rd ACM Symp. on Theory of Computing, STOC 2001, pp. 453-461 · Zbl 1323.90059
[30] L. Trevisan, Approximation algorithms for unique games, in: Proceedings of the 46th Annual Symposium on Foundations of Computer Science, FOCS 2005, 2005, pp. 197-205
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.