Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph
arXiv:1407.6958 · doi:10.1016/j.dam.2015.04.030
Abstract
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 the rank of a divisor on a graph is NP-hard. The determination of the rank of a divisor can be translated to a question about a chip-firing game on the same underlying graph. We prove the NP-hardness of this question by relating chip-firing on directed and undirected graphs.
Cited by in corpus (6)
- Root system chip-firing I: Interval-firing
- On the complexity of the chip-firing reachability problem
- Chip-firing based methods in the Riemann--Roch theory of directed graphs
- Abelian logic gates
- On approximating the rank of graph divisors
- Linear time algorithm for computing the rank of divisors on cactus graphs