Document Open Access Logo

Parameterized Distributed Algorithms

Authors Ran Ben-Basat , Ken-ichi Kawarabayashi , Gregory Schwartzman

PDF
Thumbnail PDF

File

LIPIcs.DISC.2019.6.pdf
  • Filesize: 0.59 MB
  • 16 pages

Document Identifiers

Author Details

Ran Ben-Basat
  • Harvard University, Cambridge, MA, United States
Ken-ichi Kawarabayashi
  • National Institute of Informatics, Tokyo, Japan
Gregory Schwartzman
  • National Institute of Informatics, Tokyo, Japan

Funding

  • Ben-Basat, Ran: Supported by the Zuckerman Institute, the Technion Hiroshi Fujiwara Cyber Security Research center, and the Israel Cyber Directorate.
  • Kawarabayashi, Ken-ichi: Supported by JSPS Kakenhi Grant Number JP18H05291.
  • Schwartzman, Gregory: Supported by JSPS Kakenhi Grant Number JP19K20216 and JP18H05291.

Acknowledgements

The authors thank the anonymous reviewers for their helpful remarks. We also thank Keren Censor-Hillel, Guy Even, Seri Khoury, and Ariel Kulik for helpful discussion and comments.

Cite As Get BibTex

Ran Ben-Basat, Ken-ichi Kawarabayashi, and Gregory Schwartzman. Parameterized Distributed Algorithms. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.DISC.2019.6

Abstract

In this work, we initiate a thorough study of graph optimization problems parameterized by the output size in the distributed setting. In such a problem, an algorithm decides whether a solution of size bounded by k exists and if so, it finds one. We study fundamental problems, including Minimum Vertex Cover (MVC), Maximum Independent Set (MaxIS), Maximum Matching (MaxM), and many others, in both the LOCAL and CONGEST distributed computation models. We present lower bounds for the round complexity of solving parameterized problems in both models, together with optimal and near-optimal upper bounds.
Our results extend beyond the scope of parameterized problems. We show that any LOCAL (1+epsilon)-approximation algorithm for the above problems must take Omega(epsilon^{-1}) rounds. Joined with the (epsilon^{-1}log n)^{O(1)} rounds algorithm of [Ghaffari et al., 2017] and the Omega (sqrt{(log n)/(log log n)}) lower bound of [Fabian Kuhn et al., 2016], the lower bounds match the upper bound up to polynomial factors in both parameters. We also show that our parameterized approach reduces the runtime of exact and approximate CONGEST algorithms for MVC and MaxM if the optimal solution is small, without knowing its size beforehand. Finally, we propose the first o(n^2) rounds CONGEST algorithms that approximate MVC within a factor strictly smaller than 2.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Distributed Algorithms
  • Approximation Algorithms
  • Parameterized Algorithms

Metrics

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

Related Versions

References

  1. Amir Abboud, Keren Censor-Hillel, and Seri Khoury. Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks. In DISC, 2016. Google Scholar
  2. Mohamad Ahmadi, Fabian Kuhn, and Rotem Oshman. Distributed Approximate Maximum Matching in the CONGEST Model. In DISC, 2018. Google Scholar
  3. R. Bar-Yehuda, K. Censor-Hillel, M. Ghaffari, and G. Schwartzman. Distributed Approximation of Maximum Independent Set and Maximum Matching. In PODC, 2017. Google Scholar
  4. Reuven Bar-Yehuda, Keren Censor-Hillel, and Gregory Schwartzman. A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds. J. ACM, 2017. Google Scholar
  5. R. Ben-Basat, G. Even, K.-i. Kawarabayashi, and G. Schwartzman. A Deterministic Distributed 2-Approximation for Weighted Vertex Cover in O(log nlogΔ / log²logΔ) Rounds. In SIROCCO, 2018. Google Scholar
  6. R. Ben-Basat, G. Even, K.-i. Kawarabayashi, and G. Schwartzman. Optimal Distributed Covering Algorithms. In DISC, 2019. Google Scholar
  7. Ran Ben-Basat, Ken-ichi Kawarabayashi, and Gregory Schwartzman. Parameterized Distributed Algorithms. URL: http://arxiv.org/abs/1807.04900.
  8. Karl Bringmann and Sebastian Krinninger. A Note on Hardness of Diameter Approximation. Information Processing Letters, 2018. Google Scholar
  9. Keren Censor-Hillel, Eldar Fischer, Gregory Schwartzman, and Yadu Vasudev. Fast Distributed Algorithms for Testing Graph Properties. In DISC, 2016. Google Scholar
  10. Keren Censor-Hillel, Seri Khoury, and Ami Paz. Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model. In DISC, 2017. Google Scholar
  11. R. Chitnis, G. Cormode, H. Esfandiari, M. Hajiaghayi, A. McGregor, M. Monemizadeh, and S. Vorotnikova. Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams. In SODA, 2016. Google Scholar
  12. R. H. Chitnis, G. Cormode, M. T. Hajiaghayi, and M. Monemizadeh. Parameterized Streaming: Maximal Matching and Vertex Cover. In SODA, 2015. Google Scholar
  13. Guy Even, Orr Fischer, Pierre Fraigniaud, Tzlil Gonen, Reut Levi, Moti Medina, Pedro Montealegre, Dennis Olivetti, Rotem Oshman, Ivan Rapaport, and Ioan Todinca. Three Notes on Distributed Property Testing. In DISC, 2017. Google Scholar
  14. M. R. Fellows, A. Kulik, F. Rosamond, and H. Shachnai. Parameterized approximation via fidelity preserving transformations. J. of Computer and System Sciences, 2018. Google Scholar
  15. Manuela Fischer. Improved Deterministic Distributed Matching via Rounding. In DISC, 2017. Google Scholar
  16. Silvio Frischknecht, Stephan Holzer, and Roger Wattenhofer. Networks Cannot Compute Their Diameter in Sublinear Time. In SODA, 2012. Google Scholar
  17. Mohsen Ghaffari and Bernhard Haeupler. Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut. In SODA, 2016. Google Scholar
  18. Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus. On the Complexity of Local Distributed Graph Problems. In STOC 2017, 2017. Google Scholar
  19. Bernhard Haeupler, Jason Li, and Goran Zuzic. Minor Excluded Network Families Admit Fast Distributed Algorithms. In PODC, 2018. Google Scholar
  20. D. G. Harris. Distributed approximation algorithms for maximum matching in graphs and hypergraphs. ArXiv e-prints, abs/1807.07645, 2018. URL: http://arxiv.org/abs/1807.07645.
  21. Janne H. Korhonen and Joel Rybicki. Deterministic Subgraph Detection in Broadcast CONGEST. In OPODIS, 2017. Google Scholar
  22. Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. Local Computation: Lower and Upper Bounds. J. ACM, 2016. Google Scholar
  23. Christoph Lenzen and Boaz Patt-Shamir. Fast Routing Table Construction Using Small Messages: Extended Abstract. In STOC, 2013. Google Scholar
  24. Christoph Lenzen and Roger Wattenhofer. Leveraging Linial’s locality limit. In DISC, 2008. Google Scholar
  25. Zvi Lotker, Boaz Patt-Shamir, and Seth Pettie. Improved Distributed Approximate Matching. J. ACM, 2015. Google Scholar
  26. Zvi Lotker, Boaz Patt-Shamir, and Adi Rosén. Distributed Approximate Matching. SIAM J. Comput., 2009. Google Scholar
  27. Dániel Marx. Parameterized complexity and approximation algorithms. The Comp. J., 2008. Google Scholar
  28. Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. Distributed verification and hardness of distributed approximation. In STOC, 2011. Google Scholar
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