×

zbMATH — the first resource for mathematics

Greed is good: Approximating independent sets in sparse and bounded-degree graphs. (English) Zbl 0866.68077
Summary: The minimum-degree greedy algorithm, or Greedy for short, is a simple and well-studied method for finding independent sets in graphs. We show that it achieves a performance ratio of \((\Delta+2)/3\) for approximating independent sets in graphs with degree bounded by \(\Delta\). The analysis yields a precise characterization of the size of the independent sets found by the algorithm as a function of the independence number, as well as a generalization of Turán’s bound. We also analyze the algorithm when run in combination with a known preprocessing technique, and obtain an improved \((2\overline d+3)/5\) performance ratio on graphs with average degree \(\overline d\), improving on the previous best \((\overline d+1)/2\) of Hochbaum. Finally, we present an efficient parallel and distributed algorithm attaining the performance guarantees of Greedy.

MSC:
68R10 Graph theory (including graph drawing) in computer science
05C35 Extremal problems in graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] N. Alon, U. Feige, A. Wigderson, and D. Zuckerman. Derandomized graph products.Computational Complexity, 5 (1): 60–75, 1995. · Zbl 0816.60070 · doi:10.1007/BF01277956
[2] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems.Proc. 33rd Ann. IEEE Symp. on Foundations of Computer Science, pages 14–23, Oct. 1992. · Zbl 0977.68539
[3] P. Berman and T. Fujito. On the approximation properties of the independent set problem in degree 3 graphs.Proc. Fourth Workshop on Algorithms and Data Structures pages 449–460. LNCS #955, Springer-Verlag, Berlin, 1995.
[4] P. Berman and M. Fürer. Approximating maximum independent set in bounded degree graphs.Proc. Fifth Ann. ACM-SIAM Symp. on Discrete Algorithms, pages 365–371, Jan. 1994. · Zbl 0873.68163
[5] R. L. Brooks. On coloring the nodes of a network.Math. Proc. Cambridge Philos. Soc., 37: 194–197, 1991. · JFM 67.0733.02 · doi:10.1017/S030500410002168X
[6] V. Chvátal.Linear Programming. Freeman, New York, 1983.
[7] V. Chvátal and C. McDiarmid. Small transversals in hypergraphs.Combinatorica, 12 (1): 19–26, 1992. · Zbl 0776.05080 · doi:10.1007/BF01191201
[8] P. Erdos. On the graph theorem of Turán (in Hungarian).Mat. Lapok 21: 249–251, 1970.
[9] A. V. Goldberg, S. A. Plotkin, and G. E. Shannon. Parallel symmetry-breaking in sparse graphs.SIAM J. Discrete Math., 1 (4): 434–446, No. 1988. · Zbl 0671.05038 · doi:10.1137/0401044
[10] J. R. Griggs. Lower bounds on the independence number in terms of the degrees.J. Combin. Theory Ser. B, 34: 22–39, 1983. · Zbl 0505.05037 · doi:10.1016/0095-8956(83)90003-5
[11] M. M. Halldórsson and J. Radhakrishnan. Improved approximations of independent sets in bounded-degree graphs.Proc. Fourth Scand. Workshop on Algorithm Theory, pages 195–206. LNCS #824, Springer-Verlag, Berlin, 1994. · Zbl 0817.68088
[12] M. M. Halldórsson and J. Radhakrishnan. Improved approximations of independent sets in bounded-degree via subgraph removal.Nordic J. Comput., 1 (4): 475–492, 1994. · Zbl 0817.68088
[13] M. M. Halldórsson and K. Yoshihara. Greedy approximations of independent sets in low degree graphs.Proc. Sixth Internat. Symp. on Algorithms and Computation, pages 152–161. LNCS #1004, Springer-Verlag, Berlin, Dec. 1995.
[14] D. S. Hochbaum. Efficient bounds for the stable set, vertex cover, and set packing problems.Discrete Appl. Math., 6: 243–254, 1983. · Zbl 0523.05055 · doi:10.1016/0166-218X(83)90080-X
[15] J. Hopcroft and R. Karp. Ann 5/2 algorithm for maximal matchings in bipartite graphs.SIAM J. Comput., 4: 225–231, 1973. · Zbl 0266.05114 · doi:10.1137/0202019
[16] D. S. Johnson. Worst case behavior of graph coloring algorithms.Proc. 5th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, pages 513–527. Congressus Numerantium, X, Utilitas Math., Winnipeg, Manitoba, 1974. · Zbl 0308.05109
[17] R. Karp and V. Ramachandran. A survey of parallel algorithms for shared-memory machines. In J. van Leeuwen, editor,Handbook of Theoretical Computer Science, volume A, Chapter 17, pages 869–941. Elsevier, Amsterdam, 1990. · Zbl 0900.68267
[18] S. Khanna, R. Motwani, M. Sudan, and U. Vazirani. On syntactic versus computational views of approximability.Proc. 35th Ann. IEEE Symp. on Foundations of Computer Science, pages 819–830, 1994. · Zbl 0915.68068
[19] E. Kubicka, G. Kubicki, and D. Kountanis. Approximation algorithms for the chromatic sum.Proc. 1st Great Lakes Computer Science Conf. LNCS #507, Springer-Verlag, Berlin, Oct. 1989.
[20] E. Lawler.Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York, 1976. · Zbl 0413.90040
[21] N. Linial. Locality in distributive algorithms.SIAM J. Comput., 21: 193–201, 1992. · Zbl 0787.05058 · doi:10.1137/0221015
[22] L. Lovász. Three short proofs in graph theory.J. Combin. Theory Ser. B, 19: 269–271, 1975. · Zbl 0322.05142 · doi:10.1016/0095-8956(75)90089-1
[23] C. McDiarmid. Colouring random graphs.Ann. Oper. Res., 1: 183–200, 1984. · Zbl 0673.05037 · doi:10.1007/BF01874388
[24] G. L. Nemhauser and L. Trotter. Vertex packings Structural properties and algorithms.Math. Programming, 8: 232–248, 1975. · Zbl 0314.90059 · doi:10.1007/BF01580444
[25] C. H. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes.J. Comput. System Sci., 43: 425–440, 1991. · Zbl 0765.68036 · doi:10.1016/0022-0000(91)90023-X
[26] 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
[27] H. U. Simon. On approximate solutions for combinatorial optimization problems.SIAM J. Discrete Math., 3 (2): 294–310, May 1990. · Zbl 0699.68077 · doi:10.1137/0403025
[28] P. Turán. On an extremal problem in graph theory (in Hungarian).Mat. Fiz. Lapok, 48: 436–452, 1941.
[29] Twentieth Century Fox.Wall Street. Motion picture, 1987.
[30] V. K. Wei. A lower bound on the stability number of a simple graph. Technical Memorandum No. 81-11217-9, Bell Laboratories, 1981.
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.