A Subexponential Algorithm for ARRIVAL

Abstract

The ARRIVAL problem is to decide the fate of a train moving along the edges of a directed graph, according to a simple (deterministic) pseudorandom walk. The problem is in $NP\cap coNP$ but not known to be in $P$. The currently best algorithms have runtime $2^{\Theta (n)}$ where $n$ is the number of vertices. This is not much better than just performing the pseudorandom walk. We develop a subexponential algorithm with runtime $2^{O(\sqrt{n}\log n)}$. We also give a polynomial-time algorithm if the graph is almost acyclic. Both results are derived from a new general approach to solve ARRIVAL instances.

13 pages, 1 figure Added a reference

References in corpus (1)

• Computations and Complexities of Tarski's Fixed Points and Supermodular Games

Cited by in corpus (1)

• A simple lower bound for ARRIVAL