Directeur(s) de thèse : Myriam Preissmann et Nicolas Bousquet
Ecole doctorale :MSTII
Date de début (souhaitée) : Automne 2018
Financements envisagés – Contexte – Partenaires éventuels :
Ecole doctorale :MSTII
Date de début (souhaitée) : Automne 2018
Financements envisagés – Contexte – Partenaires éventuels :
Description du sujet :
Local search heuristics have long been known to be extremely efficient in practice, and recent breakthrough results have shown that they also come with good theoretical guarantees in some cases. These algorithms are usually very easy to implement, once a meaningful way to locally perturb a solution has been found. One way to see this kind of algorithms is 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, if one sees 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 are at the heart of combinatorial reconfiguration. Combinatorial reconfiguration consists in transforming one solution of a given problem into another. 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 totally stored in the memory), it might be necessary to perform this transformation in small steps, 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 increasing attention over the last decade. Three questions naturally arise when we consider combinatorial reconfiguration problems:
1) Which elementary transformation guarantee the transformation of any feasible solution into any other ?
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 increasing attention over the last decade. Three questions naturally arise when we consider combinatorial reconfiguration problems:
1) Which elementary transformation guarantee the transformation of any feasible solution into any other ?
2) How many steps do we need to perform this transformation?
3) Can we efficiently find a (shortest) transformation?
During the three years of the thesis, the student will concentrate on structural and algorithmic aspects of Reconfiguration. In particular:
Combinatorial Graph Recoloring.
Two proper colorings are incident if they differ on exactly one vertex. The question is to determine if it possible, given a graph and an integer k, to transform any k-coloring into any other. And if yes, how many steps are needed? These questions are central for sampling of configurations in the antiferromagnetic Potts model in statistical physics. Longstanding open problems exist in this field, for instance the Cereceda's conjecture stating that a quadratic number of steps is enough for recoloring (d+2)-colorings of a d-denegerate graph.
Algorithmic Questions.
Let G be a graph and c_1,c_2 be two colorings of G. Many recent papers try to decide the complexity of determining if c_1 can be transformed into c_2. The complexity status (parameterized or not) remains open even for very simple classes of graphs such as (proper) interval graphs or planar graphs.
Reconfiguration and Sampling.
As we already mentioned, graph recoloring has been introduced to study sampling problems. In particular, a lower bound on the minimum length transformation between any pair of coloring provides a lower on the mixing time of the underlying Markov chain. However, the converse is not true. In order to get a rapid mixing time, we need stronger properties, in particular with respect to the connectivity of the reconfiguration graph. Informally speaking, we need a lot of transformations of the same length between any two colorings to guarantee a rapid mixing time.
Contact(s) : nicolas.bousquet@grenoble-inp.fr