ARRIVAL: a zero-player graph game in NP coNP

DOI10.1007/978-3-319-44479-6_14zbMATH Open1386.91034arXiv1605.03546OpenAlexW2547377995MaRDI QIDQ4604381FDOQ4604381

Authors: Jérôme Dohrau, Manuel Köhler, B. Gärtner, Jiří Matoušek, Emo Welzl 

Publication date: 26 February 2018

Published in: A Journey Through Discrete Mathematics (Search for Journal in Brave)

Abstract: Suppose that a train is running along a railway network, starting from a designated origin, with the goal of reaching a designated destination. The network, however, is of a special nature: every time the train traverses a switch, the switch will change its position immediately afterwards. Hence, the next time the train traverses the same switch, the other direction will be taken, so that directions alternate with each traversal of the switch. Given a network with origin and destination, what is the complexity of deciding whether the train, starting at the origin, will eventually reach the destination? It is easy to see that this problem can be solved in exponential time, but we are not aware of any polynomial-time method. In this short paper, we prove that the problem is in NP $cap$ coNP. This raises the question whether we have just failed to find a (simple) polynomial-time solution, or whether the complexity status is more subtle, as for some other well-known (two-player) graph games.

Full work available at URL: https://arxiv.org/abs/1605.03546

Recommendations

• ARRIVAL: next stop in CLS
• Did the train reach its destination: the complexity of finding a witness
• Two railway circuits: A universal circuit and an NP-difficult one
• The complexity of stochastic games
• Reachability switching games

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games involving graphs (91A43)

Cites Work

• The complexity of stochastic games
• Combinatorial optimization. Theory and algorithms.
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems
• Did the train reach its destination: the complexity of finding a witness
• An algorithmic study of switch graphs

Cited In (13)

• Reachability Switching Games
• Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets
• The stochastic arrival problem
• Unique End of Potential Line
• ARRIVAL: next stop in CLS
• Unique end of potential line
• Tracks from hell -- when finding a proof may be easier than checking it
• Generalized ARRIVAL problem for rotor walks in path multigraphs
• Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets
• Did the train reach its destination: the complexity of finding a witness
• Tracks from hell -- when finding a proof may be easier than checking it
• Further collapses in \(\mathsf{TFNP}\)
• Two railway circuits: A universal circuit and an NP-difficult one

This page was built for publication: ARRIVAL: a zero-player graph game in \(\text{NP}\cap \text{coNP}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4604381)