Vertex cover on 4-regular hyper-graphs is hard to approximate within 2 - &egr;

ABSTRACT

(MATH) We prove that Minimu Vertex Cover on 4-regular hyper-graphs (or in other words, Minimum Hitting Set where all sets have size exactly 4), is hard to approximate within $2 - &egr;. We also prove that the maximization version, in which we are allowed to pick B = pn elements in an n-vertex hyper-graph, and are asked to cover as many edges as possible, is hard to approximate within 1/(1 — (1—p)⁴) - &egr; when p &rhoe; 1/2 and within ((1—p)⁴ + p⁴)/(1 &mdadsh; (1—p)⁴) — &egr; when p ξ 1/2. From this follows that the general problem when B is part of the input is hard to approximate within 16/15 - &egr;.

REFERENCES

• 1: Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998 [doi>10.1145/278298.278306]
• 2: Sanjeev Arora , Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, Journal of the ACM (JACM), v.45 n.1, p.70-122, Jan. 1998 [doi>10.1145/273865.273901]
• 3: Mihir Bellare , Oded Goldreich , Madhu Sudan, Free Bits, PCPs, and Nonapproximability---Towards Tight Results, SIAM Journal on Computing, v.27 n.3, p.804-915, June 1998 [doi>10.1137/S0097539796302531]
• 4: I. Dinur. Vertex-cover on k-uniform hypergraphs is NP-hard to approximate to within ω(k). Manuscript, Jan. 2002.
• 5: I. Dinur and S. Safra. The importance of being biased. Technical Report TR01-104, Electronic Colloquium on Computational Complexity, Dec. 2001.
• 6: Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998 [doi>10.1145/285055.285059]
• 7: Uriel Feige , Shafi Goldwasser , Laszlo Lovász , Shmuel Safra , Mario Szegedy, Interactive proofs and the hardness of approximating cliques, Journal of the ACM (JACM), v.43 n.2, p.268-292, March 1996 [doi>10.1145/226643.226652]
• 8: V. Guruswami , J. Hastad , M. Sudan, Hardness of approximate hypergraph coloring, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.149, November 12-14, 2000
• 9: V. Guruswami and S. Khot. Personal communication.
• 10: Eran Halperin, Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.329-337, January 09-11, 2000, San Francisco, California, United States
• 11: Johan Håstad, Some optimal inapproximability results, Journal of the ACM (JACM), v.48 n.4, p.798-859, July 2001 [doi>10.1145/502090.502098]
• 12: J. Holmerin. Improved inapproximability results for vertex cover on k-regular hyper-graphs. Manuscript, Dec. 2001.
• 13: D. S. Johnson. Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci., 9:256--278, Dec. 1974.
• 14: M. Langberg. Approximation algorithms for maximization problems arising in graph partitioning. Master's thesis, Feinberg Graduate School, Weizmann Institute of Science, Dec. 1998.
• 15: C. H. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes. J. Comput. Syst. Sci., 43(3):425--440, Dec. 1991.
• 16: Erez Petrank, The hardness of approximation: gap location, Computational Complexity, v.4 n.2, p.133-157, April 1994 [doi>10.1007/BF01202286]
• 17: Ran Raz, A Parallel Repetition Theorem, SIAM Journal on Computing, v.27 n.3, p.763-803, June 1998 [doi>10.1137/S0097539795280895]
• 18: Ran Raz , Shmuel Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.475-484, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258641]
• 19: Luca Trevisan, Non-approximability results for optimization problems on bounded degree instances, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.453-461, July 2001, Hersonissos, Greece [doi>10.1145/380752.380839]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Hypergraphs

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

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

General Terms:
Algorithms, Experimentation, Performance, Theory