×

zbMATH — the first resource for mathematics

Approximating the independence number via the \(\vartheta\)-function. (English) Zbl 0895.90169
Summary: We describe an approximation algorithm for the independence number of a graph. If a graph on \(n\) vertices has an independence number \(n/k+m\) for some fixed integer \(k\geq 3\) and some \(m>0\), the algorithm finds, in random polynomial time, an independent set of size \(\widetilde{\Omega} (m^{3/(k+1)})\), improving the best known previous algorithm of Boppana and Halldorsson that finds an independent set of size \(\Omega(m^{1/(k-1)})\) in such a graph. The algorithm is based on semi-definite programming, some properties of the Lovász \(\vartheta\)-function of a graph and the recent algorithm of Karger, Motwani and Sudan for approximating the chromatic number of a graph. If the \(\vartheta\)-function of an \(n\) vertex graph is at least \(Mn^{1-2/k}\) for some absolute constant \(M\), we describe another, related, efficient algorithm that finds an independent set of size \(k\). Several examples show the limitations of the approach and the analysis together with some related arguments supply new results on the problem of estimating the largest possible ratio between the \(\vartheta\)-function and the independence number of a graph on \(n\) vertices.

MSC:
90C35 Programming involving graphs or networks
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] N. Alon, Explicit Ramsey graphs and orthonormal labelings,The Electronic Journal of Combinatorics 1 (1994) R12. · Zbl 0814.05056
[2] N. Alon and Y. Peres, Euclidean Ramsey theory and a construction of Bourgain,Acta Mathematica Hungarica 57 (1991) 61–64. · Zbl 0748.05070
[3] S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy, Proof verification and intractability of approximation problems, in:Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science (IEEE Computer Society Press, Los Alamitos, CA, 1992) 14–23. · Zbl 0977.68539
[4] S. Arora and S. Safra, Probabilistic checking of proofs; a new characterization of NP, in:Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science (IEEE Computer Society Press, Los Alamitos, CA, 1992) 2–13. · Zbl 0945.68516
[5] B. Berger and J. Rompel, A better performance guarantee for approximate graph coloring,Algorithmica 5 (1990) 459–466. · Zbl 0697.68032
[6] P. Berman and G. Schnitger, On the complexity of approximating the independent set problem,Information and Computation 96 (1992) 77–94. · Zbl 0804.90121
[7] R. Boppana and M.M. Halldorsson, Approximating maximum independent sets by excluding subgraphs,BIT 32 (1992) 180–196. · Zbl 0761.68044
[8] P. Erdös, Some remarks on chromatic graphs,Colloquium Mathematicum 16 (1967) 253–256.
[9] P. Erdös and G. Szekeres, A combinatorial problem in geometry,Compositio Mathematica 2 (1935) 463–470. · Zbl 0012.27010
[10] U. Feige, Randomized graph products, chromatic numbers, and the Lovász-function, in:27th Annual ACM Symposium on Theory of Computing (ACM Press, New York, 1995) 635–640. · Zbl 1058.94517
[11] U. Feige, S. Goldwasser, L. Lovász, S. Safra and M. Szegedy, Approximating Clique is almost NP-complete, in:Proceedings of the 32nd IEEE Symposium on Foundations of Computer Science (IEEE Computer Society Press, Los Alamitos, CA, 1991) 2–12.
[12] P. Frankl and V. Rödl, Forbidden intersections,Transactions AMS 300 (1987) 259–286.
[13] M. Goemans and D. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming,Journal ACM 42 (1995) 1115–1145. · Zbl 0885.68088
[14] G.H. Golub and C.F. Van Loan,Matrix Computations (The Johns Hopkins University Press, Baltimore, 1989). · Zbl 0733.65016
[15] M.M. Halldorsson, A still better performance guarantee for approximate graph coloring,Information Processing Letters 45 (1993) 19–23. · Zbl 0768.68043
[16] J. Håstad, Clique is hard to approximate withinn 1-{\(\epsilon\)},Proc. 37th IEEE FOCS (IEEE, 1996) 627–636.
[17] M. Grötschel, L. Lovász and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization,Combinatorica 1 (1981) 169–197. · Zbl 0492.90056
[18] D. Karger, R. Motwani and M. Sudan, Approximate graph coloring by semi-definite programming, in:35th Symposium on Foundations of Computer Science (IEEE Computer Society Press, Los Alamitos, CA, 1994) 2–13.
[19] R. Karp,Reducibility among combinatorial problems, eds. Miller and Thatcher (Plenum Press, New York, 1972). · Zbl 0366.68041
[20] B.S. Kashin and S.V. Konyagin, On systems of vectors in a Hilbert space,Trudy Mat. Inst. imeni V.A. Steklova 157 (1981) 64–67. English translation in:Proceedings of the Steklov Institute of Mathematics (AMS, 1983) 67–70. · Zbl 0474.46010
[21] D.E. Knuth, The sandwich theorem,The Electronic Journal of Combinatorics 1 (A1) (1994). · Zbl 0810.05065
[22] S.V. Konyagin, Systems of vectors in Euclidean space and an extremal problem for polynomials,Mat. Zametki 29 (1981) 63–74. English translation in:Mathematical Notes of the Academy of the USSR 29 (1981) 33–39. · Zbl 0455.15001
[23] L. Lovász, On the Shannon capacity of a graph,IEEE Transactions on Information Theory 25 (1979) 1–7. · Zbl 0395.94021
[24] M. Szegedy, A note on the number of Lovász and the generalized Delsarte bound, in:35th Symposium on Foundations of Computer Science (IEEE Computer Society Press, Los Alamitos, CA, 1994) 36–39.
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.