Helsinki Algorithms Seminar: "Distributed Recoloring" Mikaël Rabie

Weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design

Helsinki Algorithms Seminar is a weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design, broadly interpreted to cover both theoretical ideas and algorithm engineering on concrete computing platforms. In most cases we have a presentation prepared for each meeting to communicate an idea, a recent result, work-in-progress, or demo, but this should not be at the expense of discussion and simply having fun with algorithms.

Our affiliations are with Aalto University and the University of Helsinki, and accordingly our activities alternate between the Otaniemi Campus of Aalto University and the Kumpula Campus of University of Helsinki, catalyzed by the Helsinki Institute for Information Technology HIIT, under the Algorithmic Data Analysis (ADA) programme.

For the season programme, please see the seminar webpage.

**

Speaker: Mikaël Rabie

Title: Distributed Recoloring

Abstract:

Given two colorings of a graph, we consider the following question: can we re-color the graph from one coloring to the other through a series of elementary changes? Here, an elementary change, or step, consists in selecting an independent set and changing the color of each vertex to another also compatible with the colors of its neighbors.

The answer is not always positive, and it is in fact a PSPACE-complete decision problem.

In this talk, we try to quantify how considering a stable set at each step instead of a single vertex impacts the number of steps necessary for a re-coloring, and how much communication is needed in the LOCAL model (at each round, a vertex can only communicate with its neighbors, with no limitation as to the size of the messages nor the computation power of the vertex) to compute the re-coloring or decide there is none.

We also consider the question of how many extra colors are needed to make the problem always feasible, and beyond that, how the number of necessary steps decreases with the addition of colors. The case of trees is of special interest.

I will provide a collection of both positive and negative results around those questions.

This a joint work with Marthe Bonamy, Paul Ouvrard, Jukka Suomela and Jara Uitto.