ARRIVAL: A Zero-Player Graph Game in NP ∩ coNP

DOI10.1007/978-3-319-44479-6_14zbMath1386.91034arXiv1605.03546OpenAlexW2547377995MaRDI QIDQ4604381

Manuel Köhler, Jérôme Dohrau, Ji{ří} Matoušek, Ermo Welzl, Bernd Gärtner

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

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

Related Items (8)

Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets ⋮ Unique end of potential line ⋮ The stochastic arrival problem ⋮ ARRIVAL: Next Stop in CLS ⋮ Reachability Switching Games ⋮ Did the train reach its destination: the complexity of finding a witness ⋮ Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets ⋮ Unique End of Potential Line

Cites Work

• 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
• An algorithmic study of switch graphs
• The complexity of stochastic games
• Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems
• Combinatorial optimization. Theory and algorithms.

This page was built for publication: ARRIVAL: A Zero-Player Graph Game in NP ∩ coNP