Document Open Access Logo

Distributed Reconfiguration of Maximal Independent Sets

Authors Keren Censor-Hillel, Mikaël Rabie

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.135.pdf
  • Filesize: 497 kB
  • 14 pages

Document Identifiers

Author Details

Keren Censor-Hillel
  • Department of Computer Science, Technion, Israel
Mikaël Rabie
  • IRIF, Université de Paris, France
  • Aalto University, Finland

Funding

  • Censor-Hillel, Keren: This project has received funding from the European Union’s Horizon 2020 Research And Innovation Programe under grant agreement no. 755839.
  • Rabie, Mikaël: This work was supported in part by the Academy of Finland, Grant 285721 and ANR DESCARTES (ref. DS0702-2016).

Acknowledgements

The authors thank Alkida Balliu, Michal Dory, Seri Khoury, Dennis Olivetti, and Jukka Suomela for helpful discussions.

Cite AsGet BibTex

Keren Censor-Hillel and Mikaël Rabie. Distributed Reconfiguration of Maximal Independent Sets. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 135:1-135:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.135

Abstract

In this paper, we investigate a distributed maximal independent set (MIS) reconfiguration problem, in which there are two maximal independent sets for which every node is given its membership status, and the nodes need to communicate with their neighbors in order to find a reconfiguration schedule that switches from the first MIS to the second. Such a schedule is a list of independent sets that is restricted by forbidding two neighbors to change their membership status at the same step. In addition, these independent sets should provide some covering guarantee. We show that obtaining an actual MIS (and even a 3-dominating set) in each intermediate step is impossible. However, we provide efficient solutions when the intermediate sets are only required to be independent and 4-dominating, which is almost always possible, as we fully characterize. Consequently, our goal is to pin down the tradeoff between the possible length of the schedule and the number of communication rounds. We prove that a constant length schedule can be found in O(MIS+R32) rounds, where MIS is the complexity of finding an MIS in a worst-case graph and R32 is the complexity of finding a (3,2)-ruling set. For bounded degree graphs, this is O(log^*n) rounds and we show that it is necessary. On the other extreme, we show that with a constant number of rounds we can find a linear length schedule.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Distributed algorithms
Keywords
  • distributed graph algorithms
  • reconfiguration
  • maximal independent set

Metrics

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

Related Versions

References

  1. Noga Alon, László Babai, and Alon Itai. A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem. J. Algorithms, 7(4):567-583, 1986. URL: http://dx.doi.org/10.1016/0196-6774(86)90019-2.
  2. Baruch Awerbuch, Andrew V. Goldberg, Michael Luby, and Serge A. Plotkin. Network Decomposition and Locality in Distributed Computation. In 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989, pages 364-369, 1989. URL: http://dx.doi.org/10.1109/SFCS.1989.63504.
  3. Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, and Jukka Suomela. Lower bounds for maximal matchings and maximal independent sets. arXiv preprint, 2019. URL: http://arxiv.org/abs/1901.02441.
  4. Leonid Barenboim, Michael Elkin, and Uri Goldenberg. Locally-Iterative Distributed (Δ+ 1): -Coloring below Szegedy-Vishwanathan Barrier, and Applications to Self-Stabilization and to Restricted-Bandwidth Models. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018, pages 437-446, 2018. URL: http://dx.doi.org/10.1145/3212734.3212769.
  5. Leonid Barenboim, Michael Elkin, and Fabian Kuhn. Distributed (Delta+1)-Coloring in Linear (in Delta) Time. SIAM J. Comput., 43(1):72-95, 2014. URL: http://dx.doi.org/10.1137/12088848X.
  6. Marthe Bonamy, Paul Ouvrard, Mikaël Rabie, Jukka Suomela, and Jara Uitto. Distributed Recoloring. In Ulrich Schmid and Josef Widder, editors, 32nd International Symposium on Distributed Computing (DISC 2018), volume 121 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1-12:17, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.DISC.2018.12.
  7. Keren Censor-Hillel and Mikaël Rabie. Distributed Reconfiguration of Maximal Independent Sets. arXiv preprint, 2018. URL: http://arxiv.org/abs/1810.02106.
  8. Erik D Demaine, Martin L Demaine, Eli Fox-Epstein, Duc A Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara, and Takeshi Yamada. Linear-time algorithm for sliding tokens on trees. Theoretical Computer Science, 600:132-142, 2015. Google Scholar
  9. Mohsen Ghaffari. An Improved Distributed Algorithm for Maximal Independent Set. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 270-277, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch20.
  10. Robert A Hearn and Erik D Demaine. PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. arXiv preprint, 2002. URL: http://arxiv.org/abs/cs/0205005.
  11. Takehiro Ito, Erik D Demaine, Nicholas JA Harvey, Christos H Papadimitriou, Martha Sideri, Ryuhei Uehara, and Yushi Uno. On the complexity of reconfiguration problems. Theoretical Computer Science, 412(12-14):1054-1065, 2011. Google Scholar
  12. Marcin Kamiński, Paul Medvedev, and Martin Milanič. Complexity of independent set reconfigurability problems. Theoretical computer science, 439:9-15, 2012. Google Scholar
  13. Kishore Kothapalli and Sriram V. Pemmaraju. Super-Fast 3-Ruling Sets. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2012, December 15-17, 2012, Hyderabad, India, pages 136-147, 2012. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2012.136.
  14. Fabian Kuhn, Yannic Maus, and Simon Weidner. Deterministic Distributed Ruling Sets of Line Graphs. CoRR, abs/1805.07209, 2018. URL: http://arxiv.org/abs/1805.07209.
  15. Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. Local Computation: Lower and Upper Bounds. J. ACM, 63(2):17:1-17:44, 2016. URL: http://dx.doi.org/10.1145/2742012.
  16. Nathan Linial. Distributive Graph Algorithms Global Solutions from Local Data. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science, SFCS '87, pages 331-335, Washington, DC, USA, 1987. IEEE Computer Society. URL: http://dx.doi.org/10.1109/SFCS.1987.20.
  17. Nathan Linial. Locality in Distributed Graph Algorithms. SIAM J. Comput., 21(1):193-201, 1992. URL: http://dx.doi.org/10.1137/0221015.
  18. Daniel Lokshtanov and Amer E Mouawad. The complexity of independent set reconfiguration on bipartite graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 185-195. SIAM, 2018. Google Scholar
  19. Michael Luby. A Simple Parallel Algorithm for the Maximal Independent Set Problem. SIAM J. Comput., 15(4):1036-1053, 1986. URL: http://dx.doi.org/10.1137/0215074.
  20. Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju, Talal Riaz, and Peter Robinson. Symmetry Breaking in the Congest Model: Time- and Message-Efficient Algorithms for Ruling Sets. In 31st International Symposium on Distributed Computing, DISC 2017, October 16-20, 2017, Vienna, Austria, pages 38:1-38:16, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.DISC.2017.38.
  21. Alessandro Panconesi and Aravind Srinivasan. On the Complexity of Distributed Network Decomposition. J. Algorithms, 20(2):356-374, 1996. URL: http://dx.doi.org/10.1006/jagm.1996.0017.
  22. Johannes Schneider, Michael Elkin, and Roger Wattenhofer. Symmetry breaking depending on the chromatic number or the neighborhood growth. Theor. Comput. Sci., 509:40-50, 2013. URL: http://dx.doi.org/10.1016/j.tcs.2012.09.004.
  23. Jan van den Heuvel. The complexity of change. Surveys in Combinatorics, 409(2013):127-160, 2013. 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 Imprint Privacy Contact