zbMATH — the first resource for mathematics

Using the FGLSS-reduction to prove inapproximability results for minimum vertex cover in hypergraphs. (English) Zbl 1343.68094
Goldreich, Oded (ed.), Studies in complexity and cryptography. Miscellanea on the interplay between randomness and computation. In collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 88-97 (2011).
Summary: Using known results regarding PCP, we present simple proofs of the inapproximability of vertex cover for hypergraphs. Specifically, we show that
1 Approximating the size of the minimum vertex cover in \(O(1)\)-regular hypergraphs to within a factor of 1.99999 is NP-hard.
2 Approximating the size of the minimum vertex cover in 4-regular hypergraphs to within a factor of 1.49999 is NP-hard.
Both results are inferior to known results (by L. Trevisan [in: Proceedings of the thirty-third annual ACM symposium on theory of computing, STOC 2001. New York, NY: ACM Press. 453–461 (2001; Zbl 1323.90059)] and J. Holmerin [in: Proceedings of the thirty-fourth annual ACM symposium on theory of computing, STOC 2002. New York, NY: ACM Press. 544–552 (2002; Zbl 1192.68323)]), but they are derived using much simpler proofs. Furthermore, these proofs demonstrate the applicability of the FGLSS-reduction in the context of reductions among combinatorial optimization problems.
For the entire collection see [Zbl 1220.68005].

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C65 Hypergraphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
90C27 Combinatorial optimization
Full Text: DOI
[1] Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof Verification and Intractability of Approximation Problems. JACM 45, 501–555 (1998); Preliminary Version in 33rd FOCS (1992) · Zbl 1065.68570
[2] Arora, S., Safra, S.: Probabilistic Checkable Proofs: A New Characterization of NP. JACM 45, 70–122 (1998); Preliminary Version in 33rd FOCS (1992) · Zbl 0903.68076
[3] Bellare, M., Goldreich, O., Sudan, M.: Free Bits, PCPs and Non-Approximability – Towards Tight Results. SICOMP 27(3), 804–915 (1998) · Zbl 0912.68041
[4] Dinur, I., Guruswami, V., Khot, S., Regev, O.: A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover. SICOMP 34(5), 1129–1146 (2005) · Zbl 1079.68039
[5] Dinur, I., Safra, S.: The Importance of Being Biased. manuscript, See also (2001) · Zbl 1192.68318
[6] Dinur, I., Safra, S.: The importance of being biased. In: 34th STOC, pp. 33–42 (2002) · Zbl 1192.68318
[7] Feige, U., Goldwasser, S., Lovász, L., Safra, S., Szegedy, M.: Approximating Clique is almost NP-complete. JACM 43, 268–292 (1996); Preliminary Version in 32nd FOCS (1991) · Zbl 0882.68129
[8] Goldreich, O.: Modern Cryptography, Probabilistic Proofs and Pseudorandomness. Algorithms and Combinatorics series, vol. 17. Springer, Heidelberg (1999) · Zbl 0907.94002
[9] Hastad, J.: Clique is hard to approximate within n 1 - {\(\epsilon\)} . Acta Mathematica 182, 105–142 (1999); Preliminary versions in 28th STOC (1996) and 37th FOCS (1996) · Zbl 0989.68060
[10] Hastad, J.: Some optimal in-approximability results. In: 29th STOC, pp. 1–10 (1997)
[11] Hastad, J., Khot, S.: Query efficient PCPs with Perfect Completeness. In: 42nd FOCS, pp. 610–619 (2001)
[12] Holmerin, J.: Vertex Cover on 4-regular Hypergraphs is Hard to Approximate within 2 - {\(\epsilon\)} TR01-094, ECCC (2001), See also [13] · Zbl 1192.68323
[13] Holmerin, J.: Vertex Cover on 4-regular Hypergraphs is Hard to Approximate within 2- {\(\epsilon\)}. In: 34th STOC, pp. 544–552 (2002) · Zbl 1192.68323
[14] Holmerin, J.: Improved Inapproximability Results for Vertex Cover on k-Uniform Hypergraphs. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 1005–1016. Springer, Heidelberg (2002)
[15] Khot, S., Regev, O.: Vertex Cover Might be Hard to Approximate to within 2- {\(\epsilon\)}. JCSS 74(3), 335–349 (2008); Preliminary Version in 18th Conf. on Comput. Complex (2003) · Zbl 1133.68061
[16] Petrank, E.: The Hardness of Approximations: Gap Location. Computational Complexity 4, 133–157 (1994) · Zbl 0822.68052
[17] Trevisan, L.: Non-approximability Results for Optimization Problems on Bounded-Degree Instances. In: 33rd STOC, pp. 453–461 (2001) · Zbl 1323.90059
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.