Complexity of Path Forming Games.

摘要

For a number of two player games where players alternately choose the next vertex of a simple or elementary path in a graph, the authors considers the problem to determine whether for a given game instance there is a winning strategy for the first player. The authors show several of these problems to be PSPACE-complete. In some special cases, the authors obtain polynomial time algorithms, based upon graph rewriting or an intricate form of dynamic programming, e.g. the authors show GENERALIZED GEOGRAPHY and some other PSPACE-complete problems to be linear time solvable on graphs with constant bounded treewidth.