Independent Sets in Bounded-Degree Hypergraphs | SpringerLink
Skip to main content
Springer Nature Link
Log in

Independent Sets in Bounded-Degree Hypergraphs

  • Conference paper
Algorithms and Data Structures (WADS 2007)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4619))

Included in the following conference series:

Abstract

In this paper we analyze several approaches to the Maximum Independent Set problem in hypergraphs with degree bounded by Δ. We propose a general technique that reduces the worst case analysis of certain algorithms to their performance in the case of ordinary graphs. This technique allows us to show that the greedy algorithm that corresponds to the classical greedy set cover algorithm has a performance ratio of (Δ + 1)/2. It also allows us to apply results on local search algorithms of graphs to obtain a (Δ + 1)/2 approximation for a weighted case and (Δ + 3)/5 − ε approximation for an unweighted case. We improve the bound in the weighted case to ⌈(Δ + 1)/3 ⌉ using a simple partitioning algorithm. Finally, we show that another natural greedy algorihthm, that adds vertices of minimum degree, achieves only a ratio of Δ− 1, significantly worse than on ordinary graphs.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Bazgan, C., Monnot, J., Paschos, V., Serrière, F.: On the differential approximation of MIN SET COVER. Theor. Comput. Sci. 332, 497–513 (2005)

    Article  MATH  Google Scholar 

  2. Berman, P.: A d/2 approximation for Maximum Weight Independent Set in d-claw free graphs. In: Halldórsson, M.M. (ed.) SWAT 2000. LNCS, vol. 1851, pp. 214–219. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  3. Berman, P., Fujito, T.: On Approximation Properties of the Independent Set Problem for Low Degree Graphs. Theory Comput. Syst. 32(2), 115–132 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  4. Berman, P., Fürer, M.: Approximating maximum independent set in bounded degree graphs. SODA, pp. 365–371 (1994)

    Google Scholar 

  5. Cardinal, J., Fiorini, S., Joret, G.: Tight Results on Minimum Entropy Set Cover. In: Díaz, J., Jansen, K., Rolim, J.D.P., Zwick, U. (eds.) APPROX 2006 and RANDOM 2006. LNCS, vol. 4110, Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  6. Caro, Y., Tuza, Z.: Improved lower bounds on k-independence. J. of Graph Theory 15, 99–107 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  7. Chvátal, V.: A greedy heuristic for the set-covering problem. Math. of Operat. Research. 3, 233–235 (1979)

    Article  Google Scholar 

  8. Edmonds, J.: Paths, trees and flowers. Canadian J. of Math. 17, 449–467 (1965)

    MATH  MathSciNet  Google Scholar 

  9. Feige, U.: A threshold of ln n for approximating set cover. J. of the ACM 45, 634–652 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  10. Feige, U., Lovász, L., Tetali, P.: Approximating min-sum set cover. Algorithmica 40(4), 219–234 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  11. Halldórsson, M.: Approximations of independent sets in graphs. In: Jansen, K., Rolim, J.D.P. (eds.) APPROX 1998. LNCS, vol. 1444, Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  12. Halldórsson, M.M., Lau, H.-C.: Low-degree graph partitioning via local search with applications to Constraint Satisfaction, Max Cut, and 3-Coloring. J. of Graph Alg. and Appl. 1(3), 1–13 (1997)

    Google Scholar 

  13. Halldórsson, M., Radhakrishnan, J.: Greed is good: Approximating independent sets in sparse and bounded-degree graphs. Algorithmica 18, 143–163 (1997)

    Article  Google Scholar 

  14. Halperin, E.: Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SODA (2000)

    Google Scholar 

  15. Hofmeister, T., Lefmann, H.: Approximating maximum independent sets in uniform hypergraphs. In: Brim, L., Gruska, J., Zlatuška, J. (eds.) MFCS 1998. LNCS, vol. 1450, pp. 562–570. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  16. Hurkens, C.A.J., Schrijver, A.: On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems. SIAM J. Disc.Math. 2(1), 68–72 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  17. Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9, 256–278 (1974)

    Article  MATH  Google Scholar 

  18. Krivelevich, M., Nathaniel, R., Sudakov, B.: Approximating coloring and maximum independent set in 3-uniform hypergraphs. J. of Algorithms 41, 99–113 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  19. Lovász, L.: On decomposition of graphs. Stud. Sci. Math. Hung. 1, 237–238 (1966)

    MATH  Google Scholar 

  20. Lovász, L.: On the ratio of optimal integral and fractional covers. Disc. Math. 13, 383–390 (1975)

    Article  MATH  Google Scholar 

  21. Sakai, S., Togasaki, M., Yamazaki, K.: A note on greedy algorithms for the maximum weighted independent set problem. Disc. Appl. Math. 126(2), 313–322 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  22. Thiele, T.: A lower bound on the independence number of arbitrary hypergraphs. J. of Graph Theory 32, 241–249 (1999)

    Article  MathSciNet  Google Scholar 

  23. Trevisan, L.: Non-approximability results for optimization problems on bounded degree instances. In: Proc. of the 33rd ACM STOC (2001)

    Google Scholar 

  24. Vishwanathan, S.: Private communication (1998)

    Google Scholar 

  25. Wolsey, L.A.: An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2, 385–393 (1982)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept. of Computer Science, Reykjavík University, Iceland

    Magnús M. Halldórsson

  2. Dept. of Computer Science, University of Iceland, Iceland

    Elena Losievskaja

Authors
  1. Magnús M. Halldórsson
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Elena Losievskaja
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Frank Dehne Jörg-Rüdiger Sack Norbert Zeh

Rights and permissions

Reprints and permissions

Copyright information

© 2007 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Halldórsson, M.M., Losievskaja, E. (2007). Independent Sets in Bounded-Degree Hypergraphs. In: Dehne, F., Sack, JR., Zeh, N. (eds) Algorithms and Data Structures. WADS 2007. Lecture Notes in Computer Science, vol 4619. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73951-7_24

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-73951-7_24

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-73948-7

  • Online ISBN: 978-3-540-73951-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation