Reachability problems for general rotor walks in graphs
- Authors
- Publication Date
- Dec 06, 2023
- Source
- HAL-Descartes
- Keywords
- Language
- English
- License
- Unknown
- External links
Abstract
In this thesis, we focus on the algorithmic properties of a cellular automaton known as rotor walks. This model has been introduced in two distinct ways. Firstly, as a fundamental operation within another cellular automaton known as Sandpiles, which models the collapse of a sand pile when it becomes too high. Secondly, due to its resemblance to well-studied stochastic models, such as random walks. Indeed, numerous structural properties of random walks (hitting times, cover times, etc.) are analogous to those of this completely deterministic automaton called the rotor walk. The main motivation for this thesis stems from this "derandomization" of a random process. More precisely, a rotor walk corresponds to the movement of a particle on a directed graph following the following rule: initially, an order (a numbering) is fixed on the outgoing arcs of each vertex of the graph. Once the starting position of the particle is defined, each time it is on a vertex, it leaves through the arc with the lowest value that it has not already used. Of course, if all arcs have been used, the process restarts with the lowest value arc. There is a multitude of accessibility problems on rotors, and we aim to compile a list of them in this thesis. We also provide complexity results for some of these problems. Subsequently, we turn our attention to a specific accessibility problem: ARRIVAL. Considering a graph with sinks such that there is a directed path between each vertex of the graph and at least one of these sinks, a rotor walk inevitably terminates. Unfortunately, the number of steps before this process concludes can be exponential. In 2017, Dorhau et al. introduced a problem called ARRIVAL, which seeks to determine if the particle successfully reaches a given sink. They demonstrated that it belongs to the complexity classes NP and co-NP. Being a strong candidate for polynomial algorithm resolution, we investigate this problem on a subclass of graphs where the step count of the process can be exponential: Tree-like multigraphs. These are multigraphs whose underlying undirected graph is a tree. In this context, we show that this problem can be solved in linear time, extending these results to decision versions of the ARRIVAL problem, known to be respectively NP-complete and PSPACE-complete.
