Non-approximability results for optimization problems on bounded degree instances

ABSTRACT

par>We prove some non-approximability results for restrictions of basic combinatorial optimization problems to instances of bounded “degree&r dquo;or bounded “width.” Specifically:We prove that the Max 3SAT problem on instances where each variable occurs in at most B clauses, is hard to approximate to within a factor $7/8 + O(1/\sqrt{B})$, unless $RP = NP$. H\aa stad [18] proved that the problem is approximable to within a factor $7/8 + 1/64B$ in polynomial time, and that is hard to approximate to within a factor $7/8 +1/(\log B)^{&OHgr;(1)}$. Our result uses a new randomized reduction from general instances of Max 3SAT to bounded-occurrences instances. The randomized reduction applies to other Max SNP problems as well.We observe that the Set Cover problem on instances where each set has size at most B is hard to approximate to within a factor $\ln B - O(\ln\ln B)$ unless $P=NP$. The result follows from an appropriate setting of parameters in Feige's reduction [11]. This is essentially tight in light of the existence of $(1+\ln B)$-approximate algorithms [20, 23, 9]We present a new PCP construction, based on applying parallel repetition to the ``inner verifier,'' and we provide a tight analysis for it. Using the new construction, and some modifications to known reductions from PCP to Hitting Set, we prove that Hitting Set with sets of size B is hard to approximate to within a factor $B^{1/19}$. The problem can be approximated to within a factor B [19], and it is the Vertex Cover problem for B=2. The relationship between hardness of approximation and set size seems to have not been explored before. We observe that the Independent Set problem on graphs having degree at most B is hard to approximate to within a factor $B/2^{O(sqrt{\log B})}$, unless P = NP. This follows from a comination of results by Clementi and Trevisan [28] and Reingold, Vadhan and Wigderson [27]. It had been observed that the problem is hard to approximate to within a factor $B^{&OHgr; (1)}$ unless P=NP [1]. An algorithm achieving factor $O (B)$ is also known [21, 2, 30, 16}.

REFERENCES

• 1: Noga Alon , Uriel Feige , Avi Wigderson , David Zuckerman, Derandomized graph products, Computational Complexity, v.5 n.1, p.60-75, Jan. 1995 [doi>10.1007/BF01277956]
• 2: Noga Alon , Nabil Kahale, Approximating the independence number via the j -function, Mathematical Programming: Series A and B, v.80 n.3, p.253-264, Feb. 1, 1998 [doi>10.1007/BF01581168]
• 3: N. Alon and J. Spencer. The Probabilistic Method. Wiley Interscience, 1992.
• 4: Sanjeev Arora, Probabilistic checking of proofs and hardness of approximation problems, University of California at Berkeley, Berkeley, CA, 1995
• 5: Sanjeev Arora , Carsten Lund, Hardness of approximations, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 6: 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]
• 7: M. Bellare , S. Goldwasser , C. Lund , A. Russeli, Efficient probabilistically checkable proofs and applications to approximations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.294-304, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167174]
• 8: Piotr Berman , Marek Karpinski , including We prove a number of improved inaproximability results, On Some Tighter Inapproximability Results, University of Bonn, 1998
• 9: V. Chvatal. A greedy heuristic for the set-covering problem. Mathematics of Operations Research, 4:233-235, 1979.
• 10: Andrea E. F. Clementi, Improved non-approximability results for minimum vertex cover with density constraints, Theoretical Computer Science, v.225 n.1-2, p.113-128, Aug. 28, 1999 [doi>10.1016/S0304-3975(97)00226-0]
• 11: 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]
• 12: 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]
• 13: Oded Goldreich , R. L. Graham , B. Korte, Modern Cryptography, Probabilistic Proofs, and Pseudorandomness, Springer-Verlag New York, Inc., Secaucus, NJ, 1998
• 14: V. Guruswami. Query-efficient checking of proofs and improved PCP characterizations of NP. Master Thesis, MIT Laboratory for Computer Science, 1999.
• 15: Venkatesan Guruswami , Daniel Lewin , Madhu Sudan , Luca Trevisan, A Tight Characterization of NP with 3 Query PCPs, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.8, November 08-11, 1998
• 16: Magnús M. Halldórsson, Approximations of Independent Sets in Graphs, Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization, p.1-13, July 18-19, 1998
• 17: Johan Håstad, Some optimal inapproximability results, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.1-10, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258536]
• 18: Johan Håstad, On bounded occurrence constraint satisfaction, Information Processing Letters, v.74 n.1-2, p.1-6, April 2000 [doi>10.1016/S0020-0190(00)00032-6]
• 19: D. Hochbaum. Approximation algorithms for set covering and vertex cover problems. SIAM Journal on Computing, 11:555-556, 1982.
• 20: D.S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9:256-278, 1974.
• 21: David Karger , Rajeev Motwani , Madhu Sudan, Approximate graph coloring by semidefinite programming, Journal of the ACM (JACM), v.45 n.2, p.246-265, March 1998 [doi>10.1145/274787.274791]
• 22: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 23: L. Lovasz. On the ratio of optimal integral and fractional covers. Discrete Mathematics, 13:383-390, 1975.
• 24: Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Journal of the ACM (JACM), v.41 n.5, p.960-981, Sept. 1994 [doi>10.1145/185675.306789]
• 25: Christos Papadimitriou , Mihalis Yannakakis, Optimization, approximation, and complexity classes, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.229-234, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62233]
• 26: Ran Raz, A Parallel Repetition Theorem, SIAM Journal on Computing, v.27 n.3, p.763-803, June 1998 [doi>10.1137/S0097539795280895]
• 27: O. Reingold , S. Vadhan , A. Wigderson, Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.3, November 12-14, 2000
• 28: Alex Samorodnitsky , Luca Trevisan, A PCP characterization of NP with optimal amortized query complexity, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.191-199, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335329]
• 29: M. Sudan , L. Trevisan, Probabilistically Checkable Proofs with Low Amortized Query Complexity, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.18, November 08-11, 1998
• 30: S. Vishwanathan. Personal communication to M. Halldorsson. Cited in {16}, 1996.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional 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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Performance, Theory, Verification