Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Realizability of Graph Specifications: Characterizations and Algorithms Read chapter Read first chapter

2018 | OriginalPaper | Chapter

Simple and Local Independent Set Approximation

Authors : Ravi B. Boppana, Magnús M. Halldórsson, Dror Rawitz

Published in: Structural Information and Communication Complexity

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We bound the performance guarantees that follow from Turán-like bounds for unweighted and weighted independent sets in bounded-degree graphs. In particular, a randomized approach of Boppana forms a simple 1-round distributed algorithm, as well as a streaming and preemptive online algorithm. We show it gives a tight \((\varDelta +1)/2\)-approximation in unweighted graphs of maximum degree \(\varDelta \), which is best possible for 1-round distributed algorithms. For weighted graphs, it gives only a \((\varDelta +1)\)-approximation, but a simple modification results in an asymptotic expected \(0.529 (\varDelta +1)\)-approximation. This compares with a recent, more complex \(\varDelta \)-approximation [6], which holds deterministically.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter A Distributed Algorithm for Finding Hamiltonian Cycles in Random Graphs in Time
next chapter On the Strongest Message Adversary for Consensus in Directed Dynamic Networks
Footnotes
1
\(\tilde{O}(\cdot )\) suppresses \(\log \log n\) factors.
 
Literature
1.
2.
Alon, N., Babai, L., Itai, A.: A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms 7(4), 567–583 (1986)MathSciNetCrossRef
3.
Alon, N., Spencer, J.H.: The Probabilistic Method, 4th edn. Wiley, Hoboken (2016)MATH
4.
Austrin, P., Khot, S., Safra, M.: Inapproximability of vertex cover and independent set in bounded degree graphs. In: 24th IEEE CCC, pp. 74–80 (2009)
5.
Bansal, N., Gupta, A., Guruganesh, G.: On the Lovász theta function for independent sets in sparse graphs. In: 47th ACM STOC, pp. 193–200 (2015)
6.
Bar-Yehuda, R., Censor-Hillel, K., Ghaffari, M., Schwartzman, G.: Distributed approximation of maximum independent set and maximum matching. In: PODC, pp. 165–174 (2017)
7.
Berman, P., Fujito, T.: On approximation properties of the independent set problem for low degree graphs. Theor. Comput. Syst. 32(2), 115–132 (1999)MathSciNetCrossRef
8.
Bodlaender, M.H., Halldórsson, M.M., Konrad, C., Kuhn, F.: Brief announcement: local independent set approximation. In: PODC, pp. 377–378. ACM (2016)
9.
Boppana, R.B.: Personal communication to Joel Spencer (1987)
10.
Caro, Y.: New results on the independence number. Technical report, Tel Aviv Univ. (1979)
11.
Censor-Hillel, K., Khoury, S., Paz, A.: Quadratic and near-quadratic lower bounds for the CONGEST model. In: 31st International Symposium on Distributed Computing, pp. 10:1–10:16 (2017)
12.
13.
14.
15.
Emek, Y., Halldórsson, M.M., Mansour, Y., Patt-Shamir, B., Radhakrishnan, J., Rawitz, D.: Online set packing. SIAM J. Comput. 41(4), 728–746 (2012)MathSciNetCrossRef
16.
17.
Ghaffari, M., Kuhn, F., Maus, Y.: On the complexity of local distributed graph problems. In: 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 784–797 (2017)
18.
Griggs, J.R.: Lower bounds on the independence number in terms of the degrees. J. Combin. Theor. B 34, 22–39 (1983)MathSciNetCrossRef
19.
Halldórsson, B.V., Halldórsson, M.M., Losievskaja, E., Szegedy, M.: Streaming algorithms for independent sets in sparse hypergraphs. Algorithmica 76, 490–501 (2016)MathSciNetCrossRef
20.
Halldórsson, M., Radhakrishnan, J.: Greed is good: approximating independent sets in sparse and bounded-degree graphs. Algorithmica 18(1), 145–163 (1997)MathSciNetCrossRef
21.
Halldórsson, M.M., Konrad, C.: Computing large independent sets in a single round. Distrib. Comput. 31(1), 69–82 (2018)MathSciNetCrossRef
22.
Kuhn, F., Moscibroda, T., Wattenhofer, R.: Local computation: lower and upper bounds. J. ACM 63(2), 17:1–17:44 (2016)MathSciNetCrossRef
23.
Sakai, S., Togasaki, M., Yamazaki, K.: A note on greedy algorithms for the maximum weighted independent set problem. Discrete Appl. Math. 126(2–3), 313–322 (2003)MathSciNetCrossRef
24.
Selkow, S.M.: A probabilistic lower bound on the independence number of graphs. Discrete Math. 132(1–3), 363–365 (1994)MathSciNetCrossRef
25.
Turán, P.: On an extremal problem in graph theory. Mat. Fiz. Lapok 48, 436–452 (1941). (in Hungarian)MathSciNet
26.
Wei, V.: A lower bound on the stability number of a simple graph. Technical report, Bell Laboratories (1981)
Metadata
Title
Simple and Local Independent Set Approximation
Authors
Ravi B. Boppana
Magnús M. Halldórsson
Dror Rawitz
Copyright Year
2018
Book
Structural Information and Communication Complexity

Print ISBN: 978-3-030-01324-0

Electronic ISBN: 978-3-030-01325-7

Copyright Year: 2018

DOI
https://doi.org/10.1007/978-3-030-01325-7_12

Premium Partner

    Image Credits