Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph

Viktor Kiss, Lilla Tóthmérész

Baker and Norine introduced a graph-theoretic analogue of the Riemann-Roch theory. A central notion in this theory is the rank of a divisor. In this paper we prove that computing t…