Algorithmic aspects of a chip-firing game (Q2777901)

A variant of the chip-firing game (see \textit{A. Björner} et al. [Eur. J. Comb. 12, No. 4, 283-291 (1991; Zbl 0729.05048)]), namely a slight generalization of the dollar game introduced by \textit{N. L. Biggs} [J. Algebr. Comb. 9, No. 1, 25-45 (1999; Zbl 0919.05027)] is studied. The game is played on a graph with a (possibly negative) number of chips on each vertex. A vertex can fire, i.e. give one chip to each of its neighbors, if it has at least as many chips as incident edges. There is one special vertex, called the government, which can be fired independently of the number of chips there. If only the government can fire, the configuration is called stable. A configuration is critical, if it is both stable and recurrent. In the paper under review it is proved that the number of steps needed to reach a critical configuration is polynomial in the number of edges of the graph and the number of chips in the starting configuration. The main tool used in analysing the discrete dollar game is its continuous version called the oil game, whose statics as well as dynamics are developed.