Algorithmic properties of rotor walks in graphs, and related decision models
Axe : SciLex - Software Reliability and Security
Sujet : Algorithmic properties of rotor walks in graphs, and related decision models
Directeurs de thèse : Pierre Coucheney, DAVID et David Auger, DAVID
Institution : David, LRI
Laboratoire gestionnaire : David
Doctorant : Loric Duhaze
Début : 2019
Productions scientifiques :
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. Although these were defined in different areas independently physics of dynamics, computer science), 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).
Rotor walks are an example of self-organized criticality, a concept derived from the physics of dynamical systems, characterizing the natural emergence of complex structures in a system governed by simple local laws (13) – in particular in some cellular automatons, such as abelian sandpiles. Among the existing research axes around rotor walks, there are:
- Algorithmic issues related to accessibility: the ARRIVAL problem 5, 9 consists in predicting by which vertex the rotor walk will come out of a given graph. A version of this problem with players is also addressed in 7. Finally, in the related field of sandpiles, the problem of accessibility between two configurations is studied in12.
- Study of statistical properties: there are close links 11 between rotor walks and their random analogues. Under certain assumptions, some statistical parameters of rotor walks (hitting times, occupancy frequency, etc.) are close to those obtained by random walks. Hitting times are even equal in the case of walks on trees6. Rotor walks can therefore be seen as a deterministic object that allows to simulate random behaviour. In particular, there are many works about these properties in specific graphs (e.g. 8, 1).
- Combinatorial properties and underlying algebraic structures, notably the group linked to rotor walks that acts on the rooted spanning trees of the graph, as well as various properties of transition from a local to a global setting. It is for instance proven in 10 that the (overall) sequence of sinks reached during a repeated rotor walk will follow a periodic pattern identical to that (local) of the rotors.
- Calculability properties of the model in relation to other cellular automatons, according to the different types of doors/rotors which are present(e.g. 14). A model quite similar to the rotor walks model is the famous (and very open) problem of the Langton ant.
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. More specifically, we shall focus on algorithmic questions related to rotor walks, especially the ARRIVAL problem 5 from different points of view. It is known that this decision problem is in complexity classes NP and co-NP, without knowning whether a polynomial algorithm to solve it exists. A recently proposed algorithm 9 improves the state of theart, but remains of exponential complexity. It will also be interesting to address this problem within specific classes of
graphs. For instance, the problem is solved in polynomial time for trees. Then, we can wonder wether this result extends to almost acyclic graphs, as in the work we have conducted 2 in the context of Simple Stochastic Games (SSG), which enjoys the same complexity status between P, NP and co-NP. Second, we will look at problems related to rotor walks involving one or two players. For instance a game model with rotors that is NP-complete with one player, and PSPACE-difficult with two was proposed in 7. Hence, there is potentially a complexity leap between these games and their random analogues such as SSGs, which will have to elucidate and generalise. Faced with these algorithmic issues, an interesting track will be to study these models for specific classes of graphs in order to obtain more effective algorithms. Important skills in graph theory will then be required. Recently, pseudo-polynomial (therefore very effective) algorithms have been developed for parity games as well as mean payoff games (4) but they do not extend to stochastic games, since randomness also induces a complexity gap from these deterministic games. However, we hope that studying the cases presented above will enlighten how to establish exact or approximate solutions of SSG or MDP, by exploiting the links between rotor walks and random walks 11. Whether or not SSG are solvable in polynomial time has been an open question for 30 years (and with significant consequences, for example in software verification), and we hope to progress towards this goal. Some supervisors of the thesis have moreover published on subject in two leading international conferences (2, 3). In the previous two objectives, we will study the scaling properties from local to global: how complex macroscopic laws (e.g. periodicity of graph outputs after a chaotic trajectory) emerge from microscopic laws (e.g. rotor periodicity on each vertex).