Reachability Problems for Rotor Walks in Graphs
Problème d'accessibilité de marches de rotors dans des graphes
Résumé
Rotors are orientations of the neighborhood of vertices in a graph that allow exploration in a deterministic, but complex way, using simple rules: rotor walks. Their study has received more and more focus in the IT community over the past decade. These deterministic processes are very promising for the progress towards a derandomization of random processes, in particular those involved in Markovian processes, a central element in many models and applications (e.g. logistics, industry, city, telecommunications). Rotors are at the crossroads of several research axes among which algorithmic questions (accessibility), statistical (simulation of random processes) and combinatorial properties or even algebraic (action of the rotor group on spanning trees of a graph). The main objective of this thesis is to study deterministic analogues of stochastic models (Markov chains, Markovian decision processes, Stochastic Games) using generalized rotor walks rather than random transitions, and in particular links between stochastic and deterministic aspects, as well as issues of algorithmic complexity.
Les rotors sont des orientations du voisinage des sommets d'un graphe qui permettent de l'explorer de façon déterministe, mais complexe, à l'aide de règles simples : les marches de rotors. Leur étude connaît un essor important dans la communauté informatique depuis une dizaine d'années. Ces processus déterministes sont très prometteurs pour progresser vers la dérandomisation des processus aléatoires, en particulier ceux qui interviennent dans les processus Markoviens, qui sont un élément central de nombreux modèles et applications (e.g. logistique, industrie, ville, télécommunications). Les rotors sont au carrefour de plusieurs axes de recherche parmi lesquels des questions d'algorithmiques (accessibilité), des propriétés statistiques (simulation de processus stochastiques) et combinatoires voire algébriques (action du groupe de rotors sur les arbres couvrants d'un graphe). L'objectif principal de cette thèse sera d'étudier des analogues déterministes de modèles stochastiques (chaînes de Markov, processus de décision markoviens, jeux stochastiques) utilisant des marches de rotor généralisées plutôt que des transitions aléatoires, et en particulier les liens entre les aspects stochastiques et déterministes, ainsi que les questions de complexité algorithmique.