2026-07-20T09:02:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23957 2025-11-12T13:24:56Z ddc:004 open_access

Temporal Explorability Games Austin, Pete Bose, Sougata Mazzocchi, Nicolas Totzke, Patrick Temporal Graphs Explorability Reachability Games Temporal graphs extend ordinary graphs with discrete time that affects the availability of edges. We consider solving games played on temporal graphs where one player aims to explore the graph, i.e., visit all vertices. The complexity depends majorly on two factors: the presence of an adversary and how edge availability is specified. We demonstrate that on static graphs, where edges are always available, solving explorability games is just as hard as solving reachability games. In contrast, on temporal graphs, the complexity of explorability coincides with generalized reachability (NP-complete for one-player and PSPACE-complete for two player games). We show that if temporal graphs are given symbolically, even one-player reachability (and thus explorability and generalized reachability) games are PSPACE-hard. For one player, all these are also solvable in PSPACE and for two players, they are in PSPACE, EXP and EXP, respectively. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pete Austin and Sougata Bose and Nicolas Mazzocchi and Patrick Totzke 2025 Is Part Of LIPIcs, Volume 348, 36th International Conference on Concurrency Theory (CONCUR 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2025.7 urn:nbn:de:0030-drops-239575 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2025.7 eng https://creativecommons.org/licenses/by/4.0/legalcode