Directed Research Project Details
Complexity and Optimal Strategies of Pathos
| Author: | Katie Ray |
|---|---|
| Date: | January 11, 2005 |
| Time: | 14:00 |
| Location: | 220 Deschutes |
| Committee: | Matt Ginsberg David Etherington Andrzej Proskurowski |
Abstract
Pathos is a game on graphs in which two players take turns removing a simple path from a graph until no edges remain. The last player to remove a path is the winner. Though many games are PSPACE Complete, various methods have been used to analyze optimal strategies. The first step in this project is to select a method of analyzing Pathos. The next step is to figure out which families of graphs that method can be applied to efficiently and develop a complete characterization for those families of graphs. In parallel to finding a method of analyzing the game when it can be done efficiently, another portion of the problem is to determine the complexity of Pathos. While this has not been completely done, we have demonstrated that a version of it is PSPACE Complete.