ARRIVAL: Next Stop in CLS

Bernd Gärtner, Thomas Dueholm Hansen, Pavel Hubáček +3

We study the computational complexity of ARRIVAL, a zero-player game on $n$-vertex switch graphs introduced by Dohrau, Gärtner, Kohler, Matoušek, and Welzl. They showed that the pr…