Skip to main content
SpringerLink
Log in

Greed is good: Approximating independent sets in sparse and bounded-degree graphs

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

Theminimum-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 (Δ+2)/3 for approximating independent sets in graphs with degree bounded by Δ. 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\bar d + 3)/5\) performance ratio on graphs with average degree\(\bar d\), improving on the previous best\((\bar d + 1)/2\) of Hochbaum. Finally, we present an efficient parallel and distributed algorithm attaining the performance guarantees of Greedy.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. N. Alon, U. Feige, A. Wigderson, and D. Zuckerman. Derandomized graph products.Computational Complexity, 5 (1): 60–75, 1995.

    Article  MATH  MathSciNet  Google Scholar 

  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.

  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.

    Google Scholar 

  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.

  5. R. L. Brooks. On coloring the nodes of a network.Math. Proc. Cambridge Philos. Soc., 37: 194–197, 1991.

    Article  MathSciNet  Google Scholar 

  6. V. Chvátal.Linear Programming. Freeman, New York, 1983.

    MATH  Google Scholar 

  7. V. Chvátal and C. McDiarmid. Small transversals in hypergraphs.Combinatorica, 12 (1): 19–26, 1992.

    Article  MATH  MathSciNet  Google Scholar 

  8. P. Erdős. On the graph theorem of Turán (in Hungarian).Mat. Lapok 21: 249–251, 1970.

    MathSciNet  Google Scholar 

  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.

    Article  MATH  MathSciNet  Google Scholar 

  10. J. R. Griggs. Lower bounds on the independence number in terms of the degrees.J. Combin. Theory Ser. B, 34: 22–39, 1983.

    Article  MATH  MathSciNet  Google Scholar 

  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.

    Google Scholar 

  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.

    MATH  MathSciNet  Google Scholar 

  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.

    Google Scholar 

  14. D. S. Hochbaum. Efficient bounds for the stable set, vertex cover, and set packing problems.Discrete Appl. Math., 6: 243–254, 1983.

    Article  MATH  MathSciNet  Google Scholar 

  15. J. Hopcroft and R. Karp. Ann 5/2 algorithm for maximal matchings in bipartite graphs.SIAM J. Comput., 4: 225–231, 1973.

    Article  MathSciNet  Google Scholar 

  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.

  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.

    Google Scholar 

  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.

  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.

    Google Scholar 

  20. E. Lawler.Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York, 1976.

    MATH  Google Scholar 

  21. N. Linial. Locality in distributive algorithms.SIAM J. Comput., 21: 193–201, 1992.

    Article  MATH  MathSciNet  Google Scholar 

  22. L. Lovász. Three short proofs in graph theory.J. Combin. Theory Ser. B, 19: 269–271, 1975.

    Article  MATH  Google Scholar 

  23. C. McDiarmid. Colouring random graphs.Ann. Oper. Res., 1: 183–200, 1984.

    Article  MATH  Google Scholar 

  24. G. L. Nemhauser and L. Trotter. Vertex packings Structural properties and algorithms.Math. Programming, 8: 232–248, 1975.

    Article  MATH  MathSciNet  Google Scholar 

  25. C. H. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes.J. Comput. System Sci., 43: 425–440, 1991.

    Article  MATH  MathSciNet  Google Scholar 

  26. J. B. Shearer. A note on the independence number of triangle-free graphs.Discrete Math., 46: 83–87, 1983.

    Article  MATH  MathSciNet  Google Scholar 

  27. H. U. Simon. On approximate solutions for combinatorial optimization problems.SIAM J. Discrete Math., 3 (2): 294–310, May 1990.

    Article  MATH  MathSciNet  Google Scholar 

  28. P. Turán. On an extremal problem in graph theory (in Hungarian).Mat. Fiz. Lapok, 48: 436–452, 1941.

    MATH  MathSciNet  Google Scholar 

  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.

Download references

Author information

Authors and Affiliations

  1. Science Institute, University of Iceland, IS-107, Reykjavik, Iceland

    M. M. Halldórsson

  2. Tata Institute of Fundamental Research, Theoretical Computer Science Group, 400 005, Mumbai, India

    J. Radhakrishnan

Authors
  1. M. M. Halldórsson
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J. Radhakrishnan
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by M. X. Goemans.

Gordon Gekko [29].

A preliminary version of this paper appeared at the 26th ACM Symposium on Theory of Computing, 1994. This work was done while both authors were at the Japan Advanced Institute of Science and Technology, Hokuriku.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Halldórsson, M.M., Radhakrishnan, J. Greed is good: Approximating independent sets in sparse and bounded-degree graphs. Algorithmica 18, 145–163 (1997). https://doi.org/10.1007/BF02523693

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02523693

Key Words

Search

Navigation