Document Open Access Logo

A Subexponential Algorithm for ARRIVAL

Authors Bernd Gärtner , Sebastian Haslebacher , Hung P. Hoang

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.69.pdf
  • Filesize: 0.76 MB
  • 14 pages

Document Identifiers

Author Details

Bernd Gärtner
  • Institute of Theoretical Computer Science, Department of Computer Science, ETH Zürich, Switzerland
Sebastian Haslebacher
  • Department of Computer Science, ETH Zürich, Switzerland
Hung P. Hoang
  • Institute of Theoretical Computer Science, Department of Computer Science, ETH Zürich, Switzerland

Acknowledgements

We thank Günter Rote for pointing out an error in an earlier version of the manuscript.

Cite AsGet BibTex

Bernd Gärtner, Sebastian Haslebacher, and Hung P. Hoang. A Subexponential Algorithm for ARRIVAL. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 69:1-69:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.69

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 𝖯. 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(√nlog 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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • Pseudorandom walks
  • reachability
  • graph games
  • switching systems

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Joshua Ani, Erik D. Demaine, Dylan H. Hendrickson, and Jayson Lynch. Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets, 2020. URL: http://arxiv.org/abs/2005.03192.
  2. Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, and Igor Razgon. A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM, 55(5):Art. 21, 19, 2008. Google Scholar
  3. Anne Condon. The complexity of stochastic games. Information and Computation, 96(2):203-224, 1992. Google Scholar
  4. Joshua Cooper, Benjamin Doerr, Joel Spencer, and Gábor Tardos. Deterministic random walks on the integers. European Journal of Combinatorics, 28(8):2072-2090, 2007. EuroComb ’05 - Combinatorics, Graph Theory and Applications. Google Scholar
  5. Chuangyin Dang, Qi Qi, and Yinyu Ye. Computations and complexities of Tarski’s fixed points and supermodular games, 2020. URL: http://arxiv.org/abs/2005.09836.
  6. Jérôme Dohrau, Bernd Gärtner, Manuel Kohler, Jiří Matoušek, and Emo Welzl. ARRIVAL: a zero-player graph game in NP ∩ coNP. In A journey through discrete mathematics, pages 367-374. Springer, Cham, 2017. Google Scholar
  7. John Fearnley, Martin Gairing, Matthias Mnich, and Rahul Savani. Reachability switching games. In 45th International Colloquium on Automata, Languages, and Programming, volume 107 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 124, 14. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018. Google Scholar
  8. John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani. Unique end of potential line. J. Comput. System Sci., 114:1-35, 2020. Google Scholar
  9. John Fearnley, Dömötör Pálvölgyi, and Rahul Savani. A faster algorithm for finding Tarski fixed points, 2020. URL: http://arxiv.org/abs/2010.02618.
  10. Bernd Gärtner, Thomas Dueholm Hansen, Pavel Hubáček, Karel Král, Hagar Mosaad, and Veronika Slívová. ARRIVAL: next stop in CLS. In 45th International Colloquium on Automata, Languages, and Programming, volume 107 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 60, 13. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018. Google Scholar
  11. Bernd Gärtner and Hung P. Hoang. ARRIVAL with two vertices per layer. Manuscript in preparation, 2021. Google Scholar
  12. Alexander E. Holroyd and James Propp. Rotor walks and Markov chains. In Algorithmic probability and combinatorics, volume 520 of Contemp. Math., pages 105-126. Amer. Math. Soc., Providence, RI, 2010. Google Scholar
  13. Marcin Jurdziński. Deciding the winner in parity games is in UP ∩ co-UP. Information Processing Letters, 68(3):119-124, 1998. Google Scholar
  14. Richard M. Karp. Reducibility among combinatorial problems. In Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), pages 85-103, 1972. Google Scholar
  15. C. S. Karthik. Did the train reach its destination: the complexity of finding a witness. Inform. Process. Lett., 121:17-21, 2017. Google Scholar
  16. Tom Leighton and Satish Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM, 46(6):787-832, 1999. Google Scholar
  17. Viacheslav B. Priezzhev, Deepak Dhar, Abhishek Dhar, and Supriya Krishnamurthy. Eulerian walkers as a model of self-organized criticality. Phys. Rev. Lett., 77:5079-5082, 1996. Google Scholar
  18. Günter Rote. Personal communication, 2020. Google Scholar
  19. Alfred Tarski. A lattice-theoretical fixpoint theorem and its applications. Pacific J. Math., 5:285-309, 1955. Google Scholar
  20. Luca Trevisan. Approximation algorithms for unique games. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), pages 197-205, 2005. Google Scholar
  21. Uri Zwick and Mike Paterson. The complexity of mean payoff games on graphs. Theoretical Computer Science, 158:343-359, 1996. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact