Document Open Access Logo

Improved Distributed Approximations for Maximum Independent Set

Authors Ken-ichi Kawarabayashi, Seri Khoury, Aaron Schild, Gregory Schwartzman

PDF
Thumbnail PDF

File

LIPIcs.DISC.2020.35.pdf
  • Filesize: 495 kB
  • 16 pages

Document Identifiers

Author Details

Ken-ichi Kawarabayashi
  • National Institute of Informatics, Tokyo, Japan
Seri Khoury
  • University of California, Berkeley, CA, USA
Aaron Schild
  • University of Washington, Seattle, WA, USA
Gregory Schwartzman
  • JAIST, Ishikawa, Japan

Funding

  • Kawarabayashi, Ken-ichi: Supported by JST ERATO Kawarabayashi Large Graph Project JPMJER1201 and by JSPS Kakenhi JP18H05291.
  • Schwartzman, Gregory: Supported by JSPS Kakenhi Grant Number JP19K20216 and JP18H052.

Cite As Get BibTex

Ken-ichi Kawarabayashi, Seri Khoury, Aaron Schild, and Gregory Schwartzman. Improved Distributed Approximations for Maximum Independent Set. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.DISC.2020.35

Abstract

We present improved results for approximating maximum-weight independent set (MaxIS) in the CONGEST and LOCAL models of distributed computing. Given an input graph, let n and Δ be the number of nodes and maximum degree, respectively, and let MIS(n,Δ) be the running time of finding a maximal independent set (MIS) in the CONGEST model. Bar-Yehuda et al. [PODC 2017] showed that there is an algorithm in the CONGEST model that finds a Δ-approximation for MaxIS in O(MIS(n,Δ)log W) rounds, where W is the maximum weight of a node in the graph, which can be as large as poly (n). Whether their algorithm is deterministic or randomized that succeeds with high probability depends on the MIS algorithm that is used as a black-box. Our results:  
1) A deterministic O(MIS(n,Δ)/ε)-round algorithm that finds a (1+ε)Δ-approximation for MaxIS in the CONGEST model. 
2) A randomized (poly(log log n)/ε)-round algorithm that finds, with high probability, a (1+ε)Δ-approximation for MaxIS in the CONGEST model. That is, by sacrificing only a tiny fraction of the approximation guarantee, we achieve an exponential speed-up in the running time over the previous best known result. 
3) A randomized O(log n⋅ poly(log log n)/ε)-round algorithm that finds, with high probability, a 8(1+ε)α-approximation for MaxIS in the CONGEST model, where α is the arboricity of the graph. For graphs of arboricity α < Δ/(8(1+ε)), this result improves upon the previous best known result in both the approximation factor and the running time. 
One may wonder whether it is possible to approximate MaxIS with high probability in fewer than poly(log log n) rounds. Interestingly, a folklore randomized ranking algorithm by Boppana implies a single round algorithm that gives an expected Δ-approximation in the CONGEST model. However, it is unclear how to convert this algorithm to one that succeeds with high probability without sacrificing a large number of rounds. For unweighted graphs of maximum degree Δ ≤ n/log n, we show a new analysis of the randomized ranking algorithm, which we combine with the local-ratio technique, to provide a O(1/ε)-round algorithm in the CONGEST model that, with high probability, finds an independent set of size at least n/((1+ε)(Δ+1)). This result cannot be extended to very high degree graphs, as we show a lower bound of Ω(log^*n) rounds for any randomized algorithm that with probability at least 1-1/log n finds an independent set of size Ω(n/Δ). This lower bound holds even for the LOCAL model. The hard instances that we use to prove our lower bound are graphs of maximum degree Δ = Ω(n/log^*n).

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Approximation algorithms
  • Theory of computation → Distributed computing models
Keywords
  • Distributed graph algorithms
  • Approximation algorithms
  • Lower bounds

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Noga Alon and Joel Spencer. The Probabilistic Method. John Wiley, 1992. Google Scholar
  2. Nir Bachrach, Keren Censor-Hillel, Michal Dory, Yuval Efron, Dean Leitersdorf, and Ami Paz. Hardness of distributed optimization. In Peter Robinson and Faith Ellen, editors, Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 238-247. ACM, 2019. URL: https://doi.org/10.1145/3293611.3331597.
  3. Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph Naor, and Baruch Schieber. A unified approach to approximating resource allocation and scheduling. Journal of the ACM (JACM), 48(5):1069-1090, 2001. Google Scholar
  4. Reuven Bar-Yehuda, Keren Censor-Hillel, Mohsen Ghaffari, and Gregory Schwartzman. Distributed approximation of maximum independent set and maximum matching. In PODC, pages 165-174. ACM, 2017. Google Scholar
  5. Reuven Bar-Yehuda, Keren Censor-Hillel, and Gregory Schwartzman. A distributed (2 + ε)-approximation for vertex cover in o(log Δ / ε log log Δ) rounds. J. ACM, 64(3):23:1-23:11, 2017. Google Scholar
  6. Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The locality of distributed symmetry breaking. J. ACM, 63(3):20:1-20:45, 2016. URL: https://doi.org/10.1145/2903137.
  7. Marijke HL Bodlaender, Magnús M Halldórsson, Christian Konrad, and Fabian Kuhn. Brief announcement: Local independent set approximation. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25-28, 2016, To Appear 2016. Google Scholar
  8. Ravi B. Boppana, Magnús M. Halldórsson, and Dror Rawitz. Simple and local independent set approximation. In SIROCCO, volume 11085 of Lecture Notes in Computer Science, pages 88-101. Springer, 2018. Google Scholar
  9. Keren Censor-Hillel, Seri Khoury, and Ami Paz. Quadratic and near-quadratic lower bounds for the CONGEST model. In 31st International Symposium on Distributed Computing, DISC 2017, October 16-20, 2017, Vienna, Austria, pages 10:1-10:16, 2017. URL: https://doi.org/10.4230/LIPIcs.DISC.2017.10.
  10. Keren Censor-Hillel, Merav Parter, and Gregory Schwartzman. Derandomizing local distributed algorithms under bandwidth restrictions. In 31st International Symposium on Distributed Computing, DISC 2017, October 16-20, 2017, Vienna, Austria, volume 91 of LIPIcs, pages 11:1-11:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.DISC.2017.11.
  11. Andrzej Czygrinow, Michal Hańćkowiak, and Wojciech Wawrzyniak. Fast distributed approximations in planar graphs. In Distributed Computing, pages 78-92. Springer, 2008. Google Scholar
  12. Mohsen Ghaffari. An improved distributed algorithm for maximal independent set. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '16, pages 270-277. SIAM, 2016. URL: http://dl.acm.org/citation.cfm?id=2884435.2884455.
  13. Mohsen Ghaffari. Distributed maximal independent set using small messages. In SODA, pages 805-820. SIAM, 2019. Google Scholar
  14. Mohsen Ghaffari. Personal communication, Feb 2020. Google Scholar
  15. Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus. On the complexity of local distributed graph problems. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 784-797, 2017. URL: https://doi.org/10.1145/3055399.3055471.
  16. Magnús M. Halldórsson and Christian Konrad. Computing large independent sets in a single round. Distributed Computing, 31(1):69-82, 2018. Google Scholar
  17. Ken-ichi Kawarabayashi, Seri Khoury, Aaron Schild, and Gregory Schwartzman. Improved distributed approximation to maximum independent set. CoRR, abs/1906.11524, 2019. URL: http://arxiv.org/abs/1906.11524.
  18. Christoph Lenzen and Roger Wattenhofer. Leveraging linial’s locality limit. In Distributed Computing, pages 394-407. Springer, 2008. Google Scholar
  19. Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193-201, 1992. Google Scholar
  20. Moni Naor. A lower bound on probabilistic algorithms for distributive ring coloring. SIAM J. Discrete Math., 4(3):409-412, 1991. URL: https://doi.org/10.1137/0404036.
  21. David Peleg. Distributed Computing: A Locality-sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000. Google Scholar
  22. Sriram V. Pemmaraju. Equitable coloring extends chernoff-hoeffding bounds. In Michel X. Goemans, Klaus Jansen, José D. P. Rolim, and Luca Trevisan, editors, Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001, volume 2129, pages 285-296. Springer, 2001. URL: https://doi.org/10.1007/3-540-44666-4_31.
  23. Václav Rozhon and Mohsen Ghaffari. Polylogarithmic-time deterministic network decomposition and distributed derandomization. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 350-363. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384298.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact