  The Graph Exploration problem asks a searcher to explore an unknown
environment. The environment is modeled as a graph, where the searcher needs to
visit each vertex beginning at some vertex $s$. Furthermore, Treasure Hunt
problems are a variation of Graph Exploration, in which the searcher needs to
find a hidden treasure, which is located at some vertex $t$. In these online
problems, any online algorithm performs poorly because it has too little
knowledge about the instance to react adequately to the requests of the
adversary. Thus, the impact of a priori knowledge is of interest. In graph
problems, one form of a priori knowledge is a map of the graph. We survey the
graph exploration and treasure hunt problem with an unlabeled map, which is an
isomorphic copy of the graph, that is provided to the searcher. We formulate
decision variants of both problems by interpreting the online problems as a
game between the online algorithm (the searcher) and the adversary. The map,
however, is not controllable by the adversary. The question is, whether the
searcher is able to explore the graph fully or find the treasure for all
possible decisions of the adversary. We prove the PSPACE-completeness of these
games, whereby we analyze the variations which ask for the mere existence of a
tour through the graph or path to the treasure and the variations that include
costs. Additionally, we analyze the complexity of related problems that relax
the path constraint, allowing multiple visits of vertices or edges, or have
additional constraints, like requiring to visit specific edges.
