| Speaker : | Mikael Rabie |
| Sorbonne Université{Lip6} | |
| Date: | 25/09/2019 |
| Time: | 2:00 pm - 3:00 pm |
| Location: | Paris-Rennes Room (EIT Digital) |
Abstract
In Graph Theory, a reconfiguration problem is as following: given two solutions of a problem and a transition definition, is there a path of acceptable solutions from the first to the second using a transition one after another? What is the length of the shortest reconfiguration path? What complexities are involved? For example, a recoloration problem asks if we can go from a coloration to another, by changing the color of a node at each transition (with the coloring still valid in the intermediate steps).
In this talk, the goal would be to consider distributed version of two reconfiguration problems: recoloring, and reconfiguring independent sets. To parallelise the process, we will accept to change the state of different nodes at once, under certain hypothesis (for example, we will recolor an independent set of nodes). The questions will be, using the LOCAL model, how much communication is needed (i.e. how much a node needs knowledge of its neighborhood) in order to produce a reconfiguration schedule of a given length.
For the distributed recoloring (DISC 2019), we prove that the addition of colors for the intermediate steps is needed for some cases in order to have a solution. I will provide the analysis of trees, where we want to go from a 3-coloring to another with the use of a 4th color. II will show that a constant schedule can be found after O(D+log* n) communications. For the reconfiguration of independent sets (ICALP 2019 Best Paper), we will present different transitions from the centralized settings, to then justify the one we use. We prove that a constant schedule can be found after O(D +log* n) communications, and a linear schedule can be found after a constant number of communications.
Those works are the result of collaborations with Marthe Bonamy, Keren Censor-Hillel, Paul Ouvrard, Jara Uitto and Jukka Suomela