Polynomial Time Algorithm for ARRIVAL on Tree-like Multigraphs

David Auger, Pierre Coucheney, Loric Duhaze

A rotor walk in a directed graph can be thought of as a deterministic version of a Markov Chain, where a pebble moves from vertex to vertex following a simple rule until a terminal…