The complexity of node blocking for dags

We consider the following modification of annihilation games called node blocking. Given a directed graph, each vertex can be occupied by at most one token. There are two types of tokens, each player can move only tokens of his type. The players alternate their moves and the current player i selects one token of type i and moves the token along a directed edge to an unoccupied vertex. If a player cannot make a move then he loses. We consider the problem of determining the complexity of the game: given an arbitrary configuration of tokens in a planar directed acyclic graph (dag), does the current player have a winning strategy? We prove that the problem is PSPACE-complete.     

SOKOBAN and other motion planning problems

We consider a natural family of motion planning problems with movable obstacles and obtain hardness results for them. Some members of the family are shown to be PSPACE-complete thus improving and extending (and also simplifying) a previous NP-hardness result of Wilfong. The family considered includes a motion planning problem which forms the basis of a popular computer game called SOKOBAN. The decision problem corresponding to SOKOBAN is shown to be NP-hard. The motion planning problems considered are related to the “warehouseman's problem” considered by Hopcroft, Schwartz and Sharir, and to geometric versions of the motion planning problem on graphs considered by Papadimitriou, Raghavan, Sudan and Tamaki.