A Subexponential Algorithm for ARRIVAL

2021/02/12 by Bernd Gärtner, Gärtner, Bernd, Sebastian Haslebacher +3 · 1 citation
Computer Science · Biochemistry, Genetics and Molecular Biology · #Complexity and Algorithms in Graphs #DNA and Biological Computing #Algorithms and Data Compression

paper · pdf · doi:10.48550/arxiv.2102.06427

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 ∩ coNP but not known to be in P. The currently best algorithms have runtime 2^Θ(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(√(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.

Citations

• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms

Cited by

• A Levelset Algorithm for 3D-Tarski

Related

• A simple lower bound for ARRIVAL
• ARRIVAL: A zero-player graph game in NP ∩ coNP
• ARRIVAL: Recursive Framework & ℓ₁-Contraction
• Polynomial Time Algorithm for ARRIVAL on Tree-like Multigraphs
• ARRIVAL: Next Stop in CLS