Graph Reconfiguration – GrR

Local search heuristics have long been known to be extremely efficient in practice. Recently, major breakthroughs have shown that good theoretical guarantees can also sometimes be obtained. Such algorithms are usually very easy to implement, once a meaningful way to locally perturb a solution has been found. They can be sketched as follows:
Start with some (non optimal) solution; Explore all the solutions that can be obtained from it by a small modification (for instance, the removal or addition of a vertex); Choose some ``better'' new solution (in a deterministic or randomized way); Repeat until a reasonable solution is obtained. This approach raises several important theoretical questions. Can the whole space of solutions be explored in this way? Equivalently, in the randomized setting, looking at the algorithm as a Markov chain, is it ergodic? Is it rapidly mixing? (i.e. can each solution be reached with a reasonable probability in a reasonable number of steps?).

These questions can be considered in the more general setting of combinatorial reconfiguration. Instead of looking for a solution to a given instance, assume a solution has already been set up. Some aspects of the instance (objective, constraints...) may change over time, especially in a dynamic environment. When that happens, one might want to reconfigure an existing solution into a new, more desirable one. For operational reasons (e.g. the data cannot be entirely stored in memory), it might be necessary to perform this transformation gradually, without losing the desired properties at any time.

The feasibility and other aspects of such step-by-step transformations have been the focus of research in the area of Combinatorial Reconfiguration. Those problems have received an ever-increasing attention over the last decade. Three questions naturally arise when we consider combinatorial reconfiguration problems:
* Which elementary modifications guarantee the transformation of any feasible solution into any other?
* How many steps do we need to perform this transformation?
* Can we efficiently find a (shortest) transformation?

These questions are the central problems in combinatorial reconfiguration theory. Reconfiguration questions are heavily related to several fields of theoretical computer science. In this project, we particularly focus on:
* Structural aspects;
* Algorithmic aspects, including polynomial, FPT and approximation algorithms;
* Consequences in enumeration;
* Applications in sampling.

The links between these research topics and reconfiguration will be detailed all along the project, as well as the applications of reconfiguration to other fields such as statistical physics or chemistry.
The project will be split in five main research directions called Work Packages (WP). These work packages are transversal to the research topics, in the sense that the objectives of each work package require several skills to be fulfilled.

The team was designed with an eye for complementary skills that will allow us to tackle all aspects of reconfiguration. During the project, we also plan to organize an international workshop and a summer school, so as to develop this research area in France, especially among young researchers.