Complexity of path-forming games (Q1210546)

Games are considered where two players alternately choose the next vertex of a simple or elementary path in a graph. Winning conditions that are studied are: the first player that is unable to move loses the game, and, player 1 wins, if and only if the resulting path has a certain length, or is a Hamiltonian path or circuit. The paper studies, for several of such games, the complexity of the following problem: given a graph (and possibly some other information, like a starting vertex), is there a winning strategy for the first player, when the game is played on this graph (with this starting vertex, etc.) In many cases, these problems are shown to be PSPACE-complete, using more or less standard techniques. In some cases, polynomial or linear time algorithms are shown to exist. The most interesting of these algorithms might be the linear time algorithm, that solves the VERTEX GENERALIZED GEOGRAPHY game on graphs with bounded treewidth. Where many NP-hard problems were known to be linear time solvable on such graphs, this result gave the first problem, known to be PSPACE-hard on general graphs and solvable in linear time on graphs with bounded treewidth. The algorithm is based on an intricate form of dynamic programming. A different technique, using graph rewriting, is used to solve EDGE GENERALIZED GEOGRAPHY on cactus graphs.