Elsevier, Theoretical Computer Science, 1(110), p. 215-245, 1993
DOI: 10.1016/0304-3975(93)90357-y
Full text: Download
For a number of two-player games where players alternately choose the next vertex of a simple or an elementary path in a graph, we consider the problem to determine whether, for a given game instance, there is a winning strategy for the first player. We show several of these problems to be PSPACE-complete. In some special cases, we obtain polynomial-time algorithms, based on graph rewriting or an intricate form of dynamic programming, e.g. we show and some other PSPACE-complete problems to be linear-time-solvable on graphs with constant bounded treewidth.