zbMATH — the first resource for mathematics

Approximating maximum independent sets by excluding subgraphs. (English) Zbl 0761.68044
Summary: An approximation algorithm for the maximum independent set problem is given, improving the best performance guarantee known to \(O(n/(\log n)^ 2)\). We also obtain the same performance guarantee for graph coloring. The results can be combined into a surprisingly strong simultaneous performance guarantee for the clique and coloring problems.
The framework of subgraph-excluding algorithms is presented. We survey the known approximation algorithm for the independent set (clique), coloring, and vertex cover problems and show how almost all fit into that framework. We show that among subgraph-excluding algorithms, the ones presented achieve the optimal asymptotic performance guarantees.

68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI
[1] M. Ajtai, J. Komlós, and E. Szemerédi.A note on Ramsey numbers. J. Combin. Theory Ser A, 29: 354–360, 1980. · Zbl 0455.05045 · doi:10.1016/0097-3165(80)90030-8
[2] S. Arora and S. Safra.Approximating clique is NP-complete. Manuscript. · Zbl 0903.68076
[3] R. Bar-Yehuda and S. Even.A 2 – loglogn/2 logn performance ratio for the weighted vertex cover problem. Technical Report #260, Technion, Haifa, Jan. 1983. · Zbl 0545.90075
[4] B. Berger and J. Rompel.A better performance guarantee for approximate graph coloring. Algorithmica, 5 (4): 459–466, 1990. · Zbl 0697.68032 · doi:10.1007/BF01840398
[5] P. Berman and G. Schnitger.On the complexity of approximating the independent set problem. Information and Computation, 96 (1): 77–94, Jan. 1992. · Zbl 0804.90121 · doi:10.1016/0890-5401(92)90056-L
[6] A. Blum.An O (n 4)approximation algorithm for 3-coloring. In Proc. 22nd Ann. ACM Symp. on Theory of Computing, pages 535–542, 1989. Submitted to J. ACM.
[7] A. Blum.Some tools for approximate 3-coloring. In Proc. 31st Ann. IEEE Symp. on Found. of Comp. Sci., pages 554–562, Oct. 1990.
[8] B. Bollobás.Random Graphs. Academic Press, 1985.
[9] R. B. Boppana and M. M. Halldórsson.Approximating maximum independent sets by excluding subgraphs. In Proc. of 2nd Scand. Workshop on Algorithm Theory. Lecture Notes in Computer Science #447, pages 13–25. Springer-Verlag, July 1990. · Zbl 0761.68044
[10] V. Chvátal.Determining the stability number of a graph. SIAM J. Comput., 6 (4), Dec. 1977.
[11] P. Erdös.Some remarks on chromatic graphs. Colloq. Math., 16: 253–256, 1967.
[12] P. Erdös and G. Szekeres.A combinatorial problem in geometry. Compositio Math., 2: 463–470, 1935. · Zbl 0012.27010
[13] U. Feige, S. Goldwasser, L. Lovász, S. Safra and M. Szegedy.Approximating clique is almost NP-complete. In Proc. 32nd Ann. IEEE Symp. on Found. of Comp. Sci., pp. 2–12, Oct. 1991.
[14] T. Gallai.Kritische graphen I. Publ. Math. Inst. Hungar. Acad. Sci., 8: 165–192, 1963. (See Bollobás, B.Extremal Graph Theory., Academic Press, 1978, page 285). · Zbl 0121.18401
[15] M. R. Garey and D. S. Johnson.Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, 1979. · Zbl 0411.68039
[16] M. M. Halldórsson.A still better performance guarantee for approximate graph coloring. Technical Report 90-44, DIMACS, June 1990.
[17] D. S. Johnson.Worst case behaviour of graph coloring algorithms. In Proc. 5th Southeastern Conf. on Combinatorics, Graph Theory, and Computing. Congressus Numerantium X, pages 513–527, 1974.
[18] N. Linial and U. Vazirani.Graph products and chromatic numbers. In Proc. 30th Ann. IEEE Symp. on Found. of Comp. Sci., pages 124–128, 1989.
[19] B. Monien and E. Speckenmeyer.Ramsey numbers and an approximation algorithm for the vertex cover problem. Acta Inf., 22: 115–123, 1985. · Zbl 0558.05044 · doi:10.1007/BF00290149
[20] J. B. Shearer.A note on the independence number of triangle-free graphs. Discrete Math., 46: 83–87, 1983. · Zbl 0516.05053 · doi:10.1016/0012-365X(83)90273-X
[21] A. Wigderson.Improving the performance guarantee for approximate graph coloring. J. ACM, 30 (4): 729–735, 1983. · Zbl 0627.68057 · doi:10.1145/2157.2158
[22] S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy.On the intractability of approximation problems. Manuscript. · Zbl 1065.68570
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.