License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2022.12
URN: urn:nbn:de:0030-drops-168103
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16810/
Go to the corresponding LIPIcs Volume Portal

Auger, David ; Coucheney, Pierre ; Duhazé, Loric

Polynomial Time Algorithm for ARRIVAL on Tree-Like Multigraphs

pdf-format:
LIPIcs-MFCS-2022-12.pdf (1 MB)

Abstract

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 vertex, or sink, has been reached. The ARRIVAL problem, as defined by Dohrau et al. [Dohrau et al., 2017], consists in determining which sink will be reached. While the walk itself can take an exponential number of steps, this problem belongs to the complexity class NP ∩ co-NP without being known to be in P. In this work, we define a class of directed graphs, namely tree-like multigraphs, which are multigraphs having the global shape of an undirected tree. We prove that in this class, ARRIVAL can be solved in almost linear time, while the number of steps of a rotor walk can still be exponential. Then, we give an application of this result to solve some deterministic analogs of stochastic models (e.g., Markovian decision processes, Stochastic Games).

BibTeX - Entry

@InProceedings{auger_et_al:LIPIcs.MFCS.2022.12,
  author =	{Auger, David and Coucheney, Pierre and Duhaz\'{e}, Loric},
  title =	{{Polynomial Time Algorithm for ARRIVAL on Tree-Like Multigraphs}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{12:1--12:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16810},
  URN =		{urn:nbn:de:0030-drops-168103},
  doi =		{10.4230/LIPIcs.MFCS.2022.12},
  annote =	{Keywords: Rotor-routing, Rotor Walk, Reachability Problem, Game Theory, Tree-like Multigraph}
}

Keywords: Rotor-routing, Rotor Walk, Reachability Problem, Game Theory, Tree-like Multigraph
Collection: 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Issue Date: 2022
Date of publication: 22.08.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI