Document Open Access Logo

Distributed Recoloring

Authors Marthe Bonamy, Paul Ouvrard, Mikaël Rabie, Jukka Suomela, Jara Uitto

PDF
Thumbnail PDF

File

LIPIcs.DISC.2018.12.pdf
  • Filesize: 451 kB
  • 17 pages

Document Identifiers

Author Details

Marthe Bonamy
  • CNRS, LaBRI, Université de Bordeaux, France
Paul Ouvrard
  • LaBRI, CNRS, Université de Bordeaux, France
Mikaël Rabie
  • Aalto University, Finland
Jukka Suomela
  • Aalto University, Finland
Jara Uitto
  • ETH Zürich, Switzerland
  • and University of Freiburg, Germany

Funding

This work was supported in part by ERC Grant No. 336495 (ACDC) and ANR project DISTANCIA (ANR-17-CE40-0015).

Cite As Get BibTex

Marthe Bonamy, Paul Ouvrard, Mikaël Rabie, Jukka Suomela, and Jara Uitto. Distributed Recoloring. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.DISC.2018.12

Abstract

Given two colorings of a graph, we consider the following problem: can we recolor the graph from one coloring to the other through a series of elementary changes, such that the graph is properly colored after each step?
We introduce the notion of distributed recoloring: The input graph represents a network of computers that needs to be recolored. Initially, each node is aware of its own input color and target color. The nodes can exchange messages with each other, and eventually each node has to stop and output its own recoloring schedule, indicating when and how the node changes its color. The recoloring schedules have to be globally consistent so that the graph remains properly colored at each point, and we require that adjacent nodes do not change their colors simultaneously.
We are interested in the following questions: How many communication rounds are needed (in the deterministic LOCAL model of distributed computing) to find a recoloring schedule? What is the length of the recoloring schedule? And how does the picture change if we can use extra colors to make recoloring easier?
The main contributions of this work are related to distributed recoloring with one extra color in the following graph classes: trees, 3-regular graphs, and toroidal grids.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
  • Theory of computation → Graph algorithms analysis
Keywords
  • Distributed Systems
  • Graph Algorithms
  • Local Computations

Metrics

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

Related Versions

References

  1. Pierre Aboulker, Marthe Bonamy, Nicolas Bousquet, and Louis Esperet. Distributed coloring in sparse graphs with fewer colours. arXiv preprint arXiv:1802.05582, 2018. Google Scholar
  2. Leonid Barenboim. Deterministic (Δ+1)-coloring in sublinear (in Δ) time in static, dynamic and faulty networks. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC), pages 345-354, 2015. Google Scholar
  3. Leonid Barenboim and Michael Elkin. Distributed graph coloring: Fundamentals and recent developments. Synthesis Lectures on Distributed Computing Theory, 4(1):1-171, 2013. Google Scholar
  4. Marthe Bonamy and Nicolas Bousquet. Recoloring graphs via tree decompositions. European Journal of Combinatorics, 69:200-213, 2018. Google Scholar
  5. Marthe Bonamy, Nicolas Bousquet, Carl Feghali, and Matthew Johnson. On a conjecture of Mohar concerning Kempe equivalence of regular graphs. arXiv preprint arXiv:1510.06964, 2015. Google Scholar
  6. Paul Bonsma and Luis Cereceda. Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Theoretical Computer Science, 410(50):5215-5226, 2009. Google Scholar
  7. Paul Bonsma, Amer E Mouawad, Naomi Nishimura, and Venkatesh Raman. The complexity of bounded length graph recoloring and CSP reconfiguration. In International Symposium on Parameterized and Exact Computation, pages 110-121. Springer, 2014. Google Scholar
  8. Nicolas Bousquet and Guillem Perarnau. Fast recoloring of sparse graphs. European Journal of Combinatorics, 52:1-11, 2016. Google Scholar
  9. Sebastian Brandt, Juho Hirvonen, Janne H Korhonen, Tuomo Lempiäinen, Patric RJ Östergård, Christopher Purcell, Joel Rybicki, Jukka Suomela, and Przemysław Uznański. LCL problems on grids. In Proceedings of the ACM Symposium on Principles of Distributed Computing, pages 101-110. ACM, 2017. Google Scholar
  10. Luis Cereceda, Jan Van den Heuvel, and Matthew Johnson. Mixing 3-colourings in bipartite graphs. European Journal of Combinatorics, 30(7):1593-1606, 2009. Google Scholar
  11. Luis Cereceda, Jan Van Den Heuvel, and Matthew Johnson. Finding paths between 3-colorings. Journal of graph theory, 67(1):69-82, 2011. Google Scholar
  12. Yi-Jung Chang, Tsvi Kopelowitz, and Seth Pettie. An exponential separation between randomized and deterministic complexity in the LOCAL model. In Foundations of Computer Science (FOCS), pages 615-624, 2016. Google Scholar
  13. Yi-Jung Chang, Wenzheng Li, and Seth Pettie. An optimal distributed (Δ+1)-coloring algorithm? In Proceedings of the 50th ACM Symposium on Theory of Computing (STOC), 2018. Google Scholar
  14. Carl Feghali, Matthew Johnson, and Daniël Paulusma. A reconfigurations analogue of Brooks' theorem and its consequences. Journal of Graph Theory, 83(4):340-358, 2016. Google Scholar
  15. Carl Feghali, Matthew Johnson, and Daniël Paulusma. Kempe equivalence of colourings of cubic graphs. European Journal of Combinatorics, 59:1-10, 2017. Google Scholar
  16. Mark Jerrum. A very simple algorithm for estimating the number of k-colorings of a low-degree graph. Random Structures &Algorithms, 7(2):157-165, 1995. Google Scholar
  17. Alfred B Kempe. On the geographical problem of the four colours. American Journal of Mathematics, 2(3):193-200, 1879. Google Scholar
  18. Michel Las Vergnas and Henri Meyniel. Kempe classes and the Hadwiger conjecture. Journal of Combinatorial Theory, Series B, 31(1):95-104, 1981. Google Scholar
  19. Daniel C McDonald. Connectedness and Hamiltonicity of graphs on vertex colorings. arXiv preprint arXiv:1507.05344, 2015. Google Scholar
  20. Gary L. Miller and John H. Reif. Parallel tree contraction part 1: Fundamentals. Advances in Computing Research, 5:47-72, 1989. Google Scholar
  21. Moni Naor and Larry Stockmeyer. What can be computed locally? SIAM Journal on Computing, 24(6):1259-1277, 1995. Google Scholar
  22. Alessandro Panconesi and Aravind Srinivasan. Improved distributed algorithms for coloring and network decomposition problems. In Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, pages 581-592. ACM, 1992. Google Scholar
  23. Alessandro Panconesi and Aravind Srinivasan. The local nature of Δ-coloring and its algorithmic applications. Combinatorica, 15(2):255-280, 1995. Google Scholar
  24. 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 About DROPS Imprint Privacy Contact