Speaker:  Matthew Farrell, Cornell University
Title: The halting problem for chip-firing on finite directed graphs
Time: 2:30 PM, Monday, November 17, 2014
Place:  Malott 206

Abstract: We consider a chip-firing game on finite directed graphs and give an answer to a question posed by Bjorner, Lovasz, and Shor in 1991: given an initial configuration of chips, how difficult is it to determine whether or not it stabilizes? The approach they took involves computing a period vector p with the property that toppling the vertices according to p results in the original configuration, and then checking if it is possible to topple according to p legally (without any of the vertices ever having negative chips). This approach is problematic because the entries of p can grow exponentially in the number of vertices. We make precise a measure of "Eulerianness'' and show that for "anti-Eulerian'' graphs you can do much better, but show that in general the problem is NP-Hard. This extends the class of graphs for which the problem is known to be quickly solvable beyond the case of "nearly'' Eulerian graphs, and gives a negative answer to the existence of a polynomial time algorithm for solving the halting problem for general finite directed graphs.