×

zbMATH — the first resource for mathematics

Clique is hard to approximate within \(n^{1-\epsilon}\). (English) Zbl 0989.68060
The author of the paper studies the possible performance of a polynomial-time approximation algorithm for the optimization version of the CLIQUE problem, traditionally denoted Max-Clique, which given a graph \(G\) and an integer \(k\) tries to identify whether there are \(k\) nodes all of which are connected in graph \(G\). The author strengthens the results of Bellare, Goldreich and Sudan who proved that, for any \(\varepsilon> 0\), Max-Clique cannot be efficiently approximated within \(n^{1/3-\varepsilon}\), to prove that, for any \(\varepsilon> 0\), Max-Clique cannot be efficiently approximated within \(n^{1-\varepsilon}\).

MSC:
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arora, S., Lund, C., Motwani, R., Sudan, M. & Szegedy, M., Proof verification and the hardness of approximation problems, in33rd Annual IEEE Symposium on Foundations of Computer Science (Pittsburgh, PA, 1992), pp. 14–23. To appear inJ. ACM. · Zbl 0977.68539
[2] Arora, S. &Safra, S., Probabilistic checking of proofs: a new characterization of NP.J. ACM, 45 (1998), 70–122. · Zbl 0903.68076
[3] Babai, L., Trading group theory for randomness, in17th Annual ACM Symposium on Theory of Computing (Providence, RI, 1985), pp. 420–429.
[4] Babai, L., Fortnow, L., Levin, L. & Szegedy, M., Checking computations in polynomial time, in23rd Annual ACM Symposium on Theory of Computing (New Orleans, LA, 1991), pp. 21–31.
[5] Babai, L., Fortnow, L. &Lund, C., Nondeterministic exponential time has two-prover interactive protocols.Comput. Complexity, 1 (1991), 3–40. · Zbl 0774.68041
[6] Bellare, M., Coppersmith, D., Håstad, J., Kiwi, M. &Sudan, M., Linearity testing in characteristic two.IEEE Trans. Inform. Theory, 42 (1996), 1781–1796. · Zbl 0867.68060
[7] Bellare, M., Goldreich, O. &Sudan, M., Free bits PCPs and nonapproximability–towards tight results.SIAM J. Comput., 27 (1998), 804–915. · Zbl 0912.68041
[8] Bellare, M., Goldwasser, S., Lund, C. & Russell, A., Efficient probabilistically checkable proofs and applications to approximation, in25th Annual ACM Symposium on Theory of Computing (San Diego, CA, 1993), pp. 294–304. · Zbl 1310.68083
[9] Bellare, M. & Sudan, M., Improved nonapproximability results, in26th Annual ACM Symposium on Theory of Computing (Montreal, 1994), pp. 184–193. · Zbl 1344.68094
[10] Ben-Or, M., Goldwasser, S., Kilian, J. & Wigderson, A., Multiprover interactive proofs. How to remove intractability, in20th Annual ACM Symposium on Theory of Computing (Chicago, IL, 1988), pp. 113–131.
[11] Berman, P. &Schnitger, G., On the complexity of approximating the independent set problem.Inform. and Comput., 96 (1992), 77–94. · Zbl 0804.90121
[12] Boppana, R. &Halldórsson, M., Approximating maximum independent sets by excluding subgraphs.BIT, 32 (1992), 180–196. · Zbl 0761.68044
[13] Bourgain, J., Walsh subspaces ofL p -product spaces, inSeminaire d’analyse fonctionnelle (1979–1980), pp. 4.1–4.9. École Polytechnique, Palaiseau, 1980.
[14] Cook, S. A., The complexity of theorem proving procedure, in3rd Annual ACM Symposium on Theory of Computing (1971), pp. 151–158.
[15] Feige, U., A threshold of lnn for approximating set cover, in28th Annual ACM Symposium on Theory of Computing (Philadelphia, PA, 1996), pp. 314–318. To appear inJ. ACM. · Zbl 0922.68067
[16] Feige, U. &Goemans, M., Approximating the value of two-prover proof systems, with applications to MAX 2SAT and MAX DICUT, in3rd Israel Symposium on the Theory of Computing and Systems (Tel Aviv, 1995), pp. 182–189. IEEE Comput. Soc. Press, Los Alamitos, CA, 1995.
[17] Feige, U., Goldwasser, S., Lovász, L., Safra, S. &Szegedy, M., Interactive proofs and the hardness of approximating cliques.J. ACM, 43 (1996), 268–292. · Zbl 0882.68129
[18] Feige, U. & Kilian, J., Two prover protocols–Low error at affordable rates, in26th Annual ACM Symposium on Theory of Computing (Montreal, 1994), pp. 172–183. · Zbl 0959.68112
[19] Feige, U., Zero-knowledge and the chromatic number, in11th Annual IEEE Conference on Computational Complexity (Philadelphia, PA, 1996), pp. 278–287.
[20] Fortnow, L., Rompel, J. & Sipser, M., On the power of multi-prover interactive protocols, in3rd IEEE Symposium on Structure in Complexity Theory (1988), pp. 156–161. · Zbl 0938.68824
[21] Garey, M. R. &Johnson, D. S.,Computers and Intractability. A Guide to the Theory of NP-completeness. W. H. Freeman, San Fransisco, CA, 1979. · Zbl 0411.68039
[22] Goemans, M. & Williamson, D., 878-approximation algorithms for Max-Cut and Max-2-SAT, in26th Annual ACM Symposium on Theory of Computing (Montreal, 1994), pp. 422–431. · Zbl 1345.68274
[23] Goldwasser, S., Micali, S. &Rackoff, C., The knowledge complexity of interactive proof systems.SIAM J. Comput., 18 (1989), 186–208. · Zbl 0677.68062
[24] Håstad, J., Testing of the long code and hardness for clique, in28th Annual ACM Symposium on Theory of Computing (Philadelphia, PA, 1996), pp. 11–19. ACM, New York, 1996. · Zbl 0922.68066
[25] –, Clique is hard to approximate withinn 1 in37th Annual IEEE Symposium on Foundations of Computer Science (Burlington, VT, 1996), pp. 627–636. IEEE Comput. Soc. Press, Les Alamitos, CA, 1996.
[26] Håstad, J., Some optimal in-approximability results, in29th Annual ACM Symposium on Theory of Computing (1997), pp. 1–10. · Zbl 0963.68193
[27] Johnson, D. S., Approximation algorithms for combinatorial, problems.J. Comput. System Sci., 9 (1974), 256–278. · Zbl 0296.65036
[28] Lund, C., Fortnow, L., Karloff, H. &Nisan, N., Algebraic methods for interactive proof systems.J. ACM, 39 (1992), 859–868. · Zbl 0799.68097
[29] Motwani, R. &Raghavan, P.,Randomized Algorithms. Cambridge Univ. Press, Cambridge, 1995. · Zbl 0849.68039
[30] Papadimitriou, C.,Computational Complexity. Addison-Wesley, Reading, MA, 1994. · Zbl 0833.68049
[31] Papadimitriou, C. &Yannakakis, M. Optimization, approximation and complexity classes,J. Comput. System Sci., 43 (1991), 425–440. · Zbl 0765.68036
[32] Raz, R., A parallel repetition theorem.SIAM J. Comput. 27 (1998), 763–803. · Zbl 0911.68082
[33] Shamir, A., IP=PSPACE.J. ACM, 39 (1992), 869–877. · Zbl 0799.68096
[34] Zuckerman, D., On unapproximable versions of NP-complete problems.SIAM J. Comput., 25 (1996), 1293–1304. · Zbl 0864.68039
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.