  Online computation is a concept to model uncertainty where not all
information on a problem instance is known in advance. An online algorithm
receives requests which reveal the instance piecewise and has to respond with
irrevocable decisions. Often, an adversary is assumed that constructs the
instance knowing the deterministic behavior of the algorithm. Thus, the
adversary is able to tailor the input to any online algorithm. From a game
theoretical point of view, the adversary and the online algorithm are players
in an asymmetric two-player game. To overcome this asymmetry, the online
algorithm is equipped with an isomorphic copy of the graph, which is referred
to as unlabeled map. By applying the game theoretical perspective on online
graph problems, where the solution is a subset of the vertices, we analyze the
complexity of these online vertex subset games. For this, we introduce a
framework for reducing online vertex subset games from TQBF. This framework is
based on gadget reductions from 3-SATISFIABILITY to the corresponding offline
problem. We further identify a set of rules for extending the
3-SATISFIABILITY-reduction and provide schemes for additional gadgets which
assure that these rules are fulfilled. By extending the gadget reduction of the
vertex subset problem with these additional gadgets, we obtain a reduction for
the corresponding online vertex subset game. At last, we provide example
reductions for online vertex subset games based on VERTEX COVER, INDEPENDENT
SET, and DOMINATING SET, proving that they are PSPACE-complete. Thus, this
paper establishes that the online version with a map of NP-complete vertex
subset problems form a large class of PSPACE-complete problems.
