ARRIVAL: a zero-player graph game in NP coNP

DOI10.1007/978-3-319-44479-6_14zbMATH Open1386.91034OpenAlexW2547377995MaRDI 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)

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

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)

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.

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

Cites work

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

Cited in

(13)

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

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)